行星碰撞

难度: Medium

给定一个整数数组 asteroids，表示在同一行的小行星。

对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。

找出碰撞后剩下的所有小行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

示例 1：

输入：asteroids = [5,10,-5]
输出：[5,10]
解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。

示例 2：

输入：asteroids = [8,-8]
输出：[]
解释：8 和 -8 碰撞后，两者都发生爆炸。

示例 3：

输入：asteroids = [10,2,-5]
输出：[10]
解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。

示例 4：

输入：asteroids = [-2,-1,1,2]
输出：[-2,-1,1,2]
解释：-2 和 -1 向左移动，而 1 和 2 向右移动。 由于移动方向相同的行星不会发生碰撞，所以最终没有行星发生碰撞。

提示：

2 <= asteroids.length <= 10⁴
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0

注意：本题与主站 735 题相同： https://leetcode-cn.com/problems/asteroid-collision/

Submission

运行时间: 31 ms

内存: 17.0 MB

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        #1.使用一个栈存放 会留下的行星 2.当前行星<0 且栈顶元素大于0时 判断爆炸情况 处理数据  如果当前行星还在 则入栈
        stack = []
        for star in asteroids:
            flag = True
            while stack and flag and star<0 and stack[-1]>0:
                flag = abs(star) > stack[-1]
                if stack[-1] <= abs(star):
                    stack.pop()
                

            if flag:
                stack.append(star)
        return stack

Explain

该题解利用栈的数据结构来模拟小行星的碰撞过程。遍历整个小行星数组，对于每一个小行星，如果当前小行星向左移动（负值），并且栈顶元素（表示当前未被销毁的小行星）向右移动（正值），则根据大小比较结果决定是否爆炸。如果栈顶小行星比当前小行星小或等于，栈顶小行星会被销毁（出栈）。如果当前小行星更大或者栈为空（或栈顶元素向左移动），则当前小行星入栈。最终栈中剩余的元素即为碰撞后剩下的小行星。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack = []  # 用于存储小行星的栈
        for star in asteroids:  # 遍历每个小行星
            flag = True  # 表示当前小行星是否会入栈
            while stack and flag and star < 0 and stack[-1] > 0:  # 当栈非空且当前小行星向左，栈顶向右时
                flag = abs(star) > stack[-1]  # 如果当前小行星的绝对值大于栈顶，则继续比较
                if stack[-1] <= abs(star):  # 如果栈顶小行星的大小不大于当前小行星，栈顶元素出栈
                    stack.pop()
            if flag:  # 如果当前小行星仍需入栈
                stack.append(star)  # 将当前小行星压入栈
        return stack  # 返回栈中剩余的小行星

Explore

在处理向左移动的小行星时，如果栈顶小行星向右移动，会进行碰撞比较。如果栈为空或栈顶小行星也向左移动，则当前小行星可以直接入栈。因此，如果数组中连续出现多个向左移动的小行星，它们不会相互碰撞，而会依次入栈。这些小行星只会与先前栈中向右移动的小行星发生碰撞比较。

算法通过使用while循环持续比较栈顶小行星和当前小行星，直到没有更多的碰撞发生（即栈顶小行星不再向右或当前小行星不再向左），或者当前小行星已完全被销毁。这种循环确保了每次碰撞后，都会重新检查新的栈顶小行星与当前小行星的关系，从而保证所有相关的小行星在进入下一步之前都已被适当处理。

因为栈顶的小行星向右，而当前小行星向左，它们会发生碰撞。如果当前小行星的绝对值大于栈顶小行星，则栈顶小行星会被销毁。弹出栈顶小行星后，需要继续检查新的栈顶小行星是否也会与当前小行星发生碰撞并可能被销毁。只有当没有更多的碰撞发生时（即当前小行星不再与新的栈顶小行星碰撞，或栈为空），当前小行星才会入栈。这确保了所有的碰撞都被处理，避免了遗漏任何碰撞情况。