LeetCode 735. Asteroid Collision - 亚马逊高频题21

We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example 1:

Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Example 2:

Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.

Example 3:

Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.

Constraints:

• 2 <= asteroids.length <= 104
• -1000 <= asteroids[i] <= 1000
• asteroids[i] != 0，

题目是关于小行星碰撞的，给定一个整型数组asteroid表示有一排小行星，对于数组中的每个数，绝对值表示小行星的大小，符号表示移动方向，正号表示向右，负号表示向左。每个小行星移动速度相同。要求找出最后的小行星状态，即经过所有可能的碰撞后剩下哪些小行星。碰撞的规则是，两个小行星相撞，体积小的爆掉，体积大继续朝原来方向移动，体积相等的两个同时爆掉。朝相同方向的小行星永远不会相撞。

根据题意，只有向右方向的小行星在左边和向左方向的小行星在右边才会相撞，如果相撞的两个小行星大小相等将一起爆掉。这个看起来很像大小括号匹配的那一题，向右移动的就像是左括号，向左移动的就像是右括号，因此本题也可以用堆栈来解。定义一个堆栈，遍历小行星数组，当遇到向右移动的小行星，由于它不可能与其左边的任意小行星相撞，因此可以直接放入堆栈中。当遇到的是向左移动的小行星，就需要看当前堆栈中的情况，如果堆栈为空则不可能与任何行星相撞，直接入栈；如堆栈不为空但栈顶的行星也是向左，也不可能相撞，也直接入栈；如果栈顶行星向右，那就会相撞，要是它比栈顶向右的行星大就一直撞下去，要是遇到相等大小的向右行星就一起爆掉。

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        st = []
        for a in asteroids:
            if a > 0:
                st.append(a)
            else:
                while st and st[-1] > 0 and -a > st[-1]:
                    st.pop()
                if st and -a == st[-1]:
                    st.pop()        
                elif not st or st[-1] < 0:
                    st.append(a)
        return st