735. Asteroid Collision

Medium

Description

給定整數陣列 asteroids 代表在同一列中的小行星。正數表示向右移動，負數表示向左移動，絕對值代表大小。兩個小行星相遇時，較小的會爆炸；若大小相同則同時爆炸。同方向的小行星永遠不會相遇。回傳碰撞後的狀態。

Example:

Input: asteroids = [5,10,-5] Output: [5,10]

Intuition#

核心思路：用堆疊處理碰撞，只有「棧頂向右、新元素向左」時才會發生碰撞，反覆比較直到碰撞結束。

向右的小行星（正數）不會和之前向右的碰撞，直接入棧
向左的小行星（負數）會和之前向右的碰撞，需要逐一比較
碰撞結果有三種：新的爆炸、棧頂爆炸、同歸於盡

Approaches#

⭐1: Stack 模擬碰撞#

概念: 遍歷小行星，正數直接 push。負數則與棧頂比較：棧頂較小就 pop 掉（繼續比較），棧頂較大就跳過新元素，一樣大就都移除
時間複雜度: O(n) - 每個小行星最多入棧出棧各一次
空間複雜度: O(n)

class Solution {
    fun asteroidCollision(asteroids: IntArray): IntArray {
        val stack = ArrayDeque<Int>()

        for (ast in asteroids) {
            var alive = true

            while (alive && ast < 0 && stack.isNotEmpty() && stack.last() > 0) {
                if (stack.last() < -ast) {
                    // 棧頂較小，爆炸
                    stack.removeLast()
                } else if (stack.last() == -ast) {
                    // 同大，同歸於盡
                    stack.removeLast()
                    alive = false
                } else {
                    // 棧頂較大，新的爆炸
                    alive = false
                }
            }

            if (alive) {
                stack.addLast(ast)
            }
        }

        return stack.toIntArray()
    }
}

🔑 Takeaways#

Pattern: 元素之間有「衝突/消除」關係時，堆疊可以有效模擬
關鍵技巧: 用布林變數 alive 追蹤新元素是否存活，清晰地處理三種碰撞結果。注意碰撞條件：只有「棧頂 > 0 且新元素 < 0」才會碰撞