Asteroid Collision

題目描述

給定整數陣列 asteroids，正數向右移，負數向左移，絕對值代表大小。碰撞時小的爆炸，相同大小都爆炸。回傳碰撞後的狀態。

輸入：asteroids = [5,10,-5]
輸出：[5,10]（10 和 -5 碰撞，10 存活）

輸入：asteroids = [8,-8]
輸出：[]（等大互毀）

輸入：asteroids = [10,2,-5]
輸出：[10]（2 和 -5 碰撞，-5 存活；然後 10 和 -5 碰撞，10 存活）

解題思路

遍歷小行星

逐一處理每顆小行星

判斷碰撞

當前為負（左飛）且 Stack 頂為正（右飛）→ 碰撞

比較大小

頂端較小 → pop 繼續檢查；當前較小 → 當前消滅；相等 → 都消滅

存活入棧

碰撞結束後若當前仍存活，push 入 Stack

程式碼

C#

csharp

public class Solution {
    public int[] AsteroidCollision(int[] asteroids) {
        var stack = new Stack<int>();
        foreach (int ast in asteroids) {
            bool alive = true;
            // 碰撞條件：當前向左(負) 且 Stack頂向右(正)
            while (alive && ast < 0 && stack.Count > 0 && stack.Peek() > 0) {
                if (stack.Peek() < -ast) {
                    stack.Pop(); // 頂端較小，爆掉，繼續檢查
                } else if (stack.Peek() == -ast) {
                    stack.Pop(); // 等大互毀
                    alive = false;
                } else {
                    alive = false; // 當前較小，當前爆掉
                }
            }
            if (alive) stack.Push(ast);
        }
        var result = stack.ToArray();
        Array.Reverse(result);
        return result;
    }
}

TypeScript

typescript

function asteroidCollision(asteroids: number[]): number[] {
    const stack: number[] = [];
    for (const ast of asteroids) {
        let alive = true;
        while (alive && ast < 0 && stack.length > 0 && stack[stack.length - 1] > 0) {
            const top = stack[stack.length - 1];
            if (top < -ast) {
                stack.pop();
            } else if (top === -ast) {
                stack.pop();
                alive = false;
            } else {
                alive = false;
            }
        }
        if (alive) stack.push(ast);
    }
    return stack;
}

Python

python

def asteroidCollision(asteroids: list[int]) -> list[int]:
    stack = []
    for ast in asteroids:
        alive = True
        while alive and ast < 0 and stack and stack[-1] > 0:
            if stack[-1] < -ast:
                stack.pop()
            elif stack[-1] == -ast:
                stack.pop()
                alive = False
            else:
                alive = False
        if alive:
            stack.append(ast)
    return stack

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(n) |

每顆小行星最多被 push 和 pop 各一次，攤銷 O(n)。

圖解

[10, 2, -5]

push 10, 2→

Stack: [10, 2]

-5 來了→

-5 vs 2 → 2爆 Stack: [10]

繼續碰撞→

-5 vs 10 → -5爆 Stack: [10]

-5 消滅→

結果: [10]

進階觀點

💡面試追問

為什麼只有「右飛遇到左飛」才碰撞？ 同向永遠追不上（速度相同），左飛在右飛左邊則越飛越遠。
alive 變數的作用？ 追蹤當前小行星是否還存活。在 while 迴圈中可能被設為 false（被撞毀或互毀）。
連鎖碰撞的例子？ [5,3,2,-10]：-10 依序撞毀 2、3、5，最後只剩 [-10]。
跟括號匹配的關係？ 都是 Stack 的經典應用 — 新元素與 Stack 頂端互動，決定 push 或 pop。

理解測驗

🤔 asteroids = [-2,-1,1,2] 的結果是什麼？

🤔 為什麼每顆小行星最多被 push 和 pop 各一次，所以時間是 O(n)？