解題說明
Asteroid Collision
題目描述:給定一個整數陣列 asteroids,每個元素代表一顆小行星。正數表示向右移動,負數表示向左移動,絕對值代表大小。兩顆相向而行的小行星會發生碰撞,較小的爆炸;若大小相同則兩顆都爆炸。回傳碰撞結束後剩餘的小行星。
解題思路:使用堆疊模擬碰撞過程。遍歷每顆小行星時,若它向右(正數),直接壓入堆疊;若它向左(負數),則需與堆疊頂部向右的小行星發生碰撞。碰撞規則:若堆疊頂部較小則彈出、相等則兩顆都消滅、頂部較大則當前小行星爆炸。反覆比較直到不再碰撞,才將倖存者壓入堆疊。關鍵觀察:只有「正數在堆疊頂,負數新進」才會碰撞,向同方向移動的小行星永遠不會相撞。
C++ 解法
複雜度分析
時間複雜度:O(n) — 每顆小行星最多被壓入和彈出堆疊各一次。
空間複雜度:O(n) — 堆疊最壞情況存放所有小行星(例如全部同向)。
虛擬碼
1. Initialize empty stack
2. For each asteroid ast:
a. Set alive = true
b. While alive and ast < 0 and stack not empty and top > 0:
- If top < -ast: pop top (top explodes)
- Else if top == -ast: pop top, alive = false (both explode)
- Else: alive = false (ast explodes)
c. If alive: push ast onto stack
3. Return stack as result array其他解法
直接陣列模擬:用索引指標代替堆疊,邏輯相同但更節省記憶體(原地修改輸入陣列)。常數因子略小但可讀性較差。
遞迴模擬:遞迴處理每次碰撞,但容易造成深度過大的呼叫堆疊(stack overflow),不推薦。
延伸思考
- 若小行星也可以靜止(速度為零),碰撞規則應如何修改?
- 如果所有小行星大小相同,最少需要幾次碰撞才能讓系統穩定?
- 如何在 O(1) 額外空間內完成此題(不使用額外堆疊)?