JZX轻语：简

LeetCode 735 - 小行星碰撞

发表于2024年04月28日

使用栈来维护存活的小行星(不难推出，这个数组中，往左走的小行星必定在所有往右走小行星的前面，否则会继续发生碰撞)。从左往右处理小行星，如果小行星往左走、仍存活、且栈顶的小行星(存活的小行星中最靠右的)往右走，则处理碰撞，直至不满足上述条件。

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack = []
        for asteroid in asteroids:
            alive = True
            # 执行循环的条件: 1. 栈内有东西 2. 该小行星左移, 且栈顶的小行星在右移 3. 该小行星还存活
            while stack and asteroid < 0 < stack[-1] and alive:
                # 循环体内, 必定和栈顶右移的小行星发生了碰撞
                if stack[-1] >= -asteroid:  # 自己被吃掉了, 不再存活
                    alive = False
                if stack[-1] <= -asteroid:  # 右移的小行星被吃掉, 出栈
                    stack.pop()
            if alive:
                stack.append(asteroid)
        return stack

闪念标签：LC

题目链接：https://leetcode.cn/problems/asteroid-collision/ - 栈