发表于 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 题目链接