735. Asteroid Collision

📘 題目敘述

給定一個整數陣列 asteroids，表示一排小行星。

• 絕對值代表大小
• 正數代表往右移動
• 負數代表往左移動

當兩顆小行星相撞時（只會發生在右走 vs 左走）：

• 小的會爆炸
• 大的會留下
• 若大小相同，兩顆都爆炸

請回傳所有碰撞結束後，剩下的小行星狀態（依原本順序）。

條件限制

• 2 ≤ asteroids.length ≤ 10^4
• -1000 ≤ asteroids[i] ≤ 1000
• asteroids[i] != 0

🧠 解題思路

這題的核心是：

只有「右走（正數）」遇到「左走（負數）」才可能相撞 其他情況（同方向、或左走在前右走在後）都不會相撞。

所以我用一個 vector<int> space 來當作「堆疊（stack）」：

• space 存的是「目前已經確定留下來、但可能還會被後面撞到」的小行星
• 每來一顆新的小行星，我就跟 space 的最後一顆（space.back()）做碰撞判斷
• 因為碰撞只會影響最右邊那一顆（最後進來的），所以 stack 很適合

所有變數

• space：模擬 stack，用來保存目前還活著的小行星序列（可能還會被後面撞）
• i：目前正在處理的那顆小行星（從 asteroids 逐個掃過來）

🪜 主要流程步驟

1. 逐顆掃描 asteroids

我用 for (int i : asteroids) 一顆一顆處理。

2. 情況一：i > 0（往右走）

• 往右走的行星不會跟左邊發生碰撞（因為它往右）
• 直接丟進 space 代表它目前先活著

3. 情況二：i < 0（往左走）

這種才可能撞到前面「往右走」的小行星，所以分幾種狀況：

(1) 不可能發生碰撞：直接加入

如果：

• space 是空的（前面沒東西）
• 或 space.back() < 0（前面最後一顆也往左走）

那代表新來的 i 不會撞到任何人，直接加入 space。

(2) 可能碰撞：space.back() > 0

這時候才會有「右走 vs 左走」的正面相撞，我用 while (!space.empty()) 連續處理：

因為 i 可能連續撞爆很多顆正數行星（像連鎖反應），所以必須一直比較。

碰撞比較只看大小：

A. -i > space.back()（左走比較大）

• 右走那顆爆炸 → space.pop_back()
• 但 i 還活著，要繼續跟新的 space.back() 比
• 如果 pop 到：
  • space 空了，或最後變成負數（往左走）
  • 代表 i 沒有人能撞了 → 把 i 放進 space

B. -i == space.back()（一樣大）

• 兩顆都爆炸
• 右走那顆 pop_back()
• i 也不加入，直接結束（break）

C. -i < space.back()（右走比較大）

• i 直接爆炸
• 不做任何事，結束（break）

4. 回傳 space

掃描完全部小行星後，space 就是最後剩下的結果。

💻 程式碼實作

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        vector<int> space;
        for (int i : asteroids) {
            if (i > 0) {
                space.push_back(i);
            } else {
                if (space.empty() || space.back() < 0) {
                    space.push_back(i);
                    continue;
                }
                while (!space.empty()) {
                    if (-i > space.back()) {
                        space.pop_back();
                        if (space.empty() || space.back() < 0) {
                            space.push_back(i);
                            break;
                        }
                    } else if (-i == space.back()) {
                        space.pop_back();
                        break;
                    } else {
                        break;
                    }
                }
            }
        }
        return space;
    }
};

🔗 題目連結

https://leetcode.com/problems/asteroid-collision/