Leetcode 連結

這題可以用堆疊（stack）來解。

從題目描述可知，行星以相同速度移動，所以我們只需要考慮它們的方向與大小。
兩顆行星是否會碰撞以及碰撞結果，可以分成三種情況：

  1. asteroids = [5, 10] 或 asteroids = [-5, -10]

    • 兩顆行星同方向移動，不會發生碰撞。

  2. asteroids = [-5, 10]

    • 兩顆行星方向不同，但不會相撞。

  3. asteroids = [5, -10]

    • 兩顆行星相向移動，會發生碰撞。

碰撞又可以進一步分成兩種結果：

  1. 大小不同： 較大的行星會留下。
    例如：asteroids = [5, -10] → asteroids = [-10]

  2. 大小相同： 兩顆行星都會消失。
    例如：asteroids = [8, -8] → asteroids = []

因此，我們只需要關注「兩顆行星相向移動並碰撞」的情況。

我們逐一走訪每顆行星，將它加入堆疊，並依據上述條件用堆疊判斷該行星應該留下還是被移除。

以下是 Python 解法：

class Solution(object):
    def asteroidCollision(self, asteroids):
        """
        :type asteroids: List[int]
        :rtype: List[int]
        """
        stack = []
        for star in asteroids:
            while stack and star < 0 and stack[-1] > 0:
                if abs(star) > abs(stack[-1]):
                    stack.pop()
                    continue
                elif abs(star) == abs(stack[-1]):
                    stack.pop()
                break
            else:
                stack.append(star)
        return stack