LeetCode 解題筆記：735. Asteroid Collision

作者：王一哲
日期：2026年9月18日


LeetCode 題目連結：735. Asteroid Collision

解題想法

中等難度題，題目給一個陣列 $asteroids$，索引值代表小行星的位置，數值的絕對值代表小行星的大小，正值代表小行星向右移動，負值代表小行星向左移動，每個小行星的速度量值都相等。如果兩個小行星碰撞，會留下較大的小行星；如果兩者一樣大，兩者一起撞掉。題目要求最後留下來的小行星資料。

這題可以用堆疊解題。先建一個 list 或 vector $st$。用 for 迴圈依序讀取小行星的大小及移動方向 $a$，如果 st 是空的、st 最後一項是負的或者st 最後一項是正的且 a 是正的，不會碰撞，直接加入 a；如果發生碰撞，再用一個 while 迴圈，檢查 $a$ 與 $st$ 最後一項的關係，再決定是否移除 $st$ 的最後一項，以及是否要將 $a$ 加入 $st$。詳細的過程請看程式碼及註解。

Python 程式碼

Runtime: 3 ms, beats 94.41%. Memory: 20.38 MB, beats 33.14%.

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        st = []
        for a in asteroids:
            # 如果 st 是空的、st 最後一項是負的或者st 最後一項是正的且 a 是正的，不會碰撞，直接加入 a
            if not st or st[-1] < 0 or (st[-1] > 0 and a > 0):
                st.append(a)
            else:  # 發生碰撞
                add_new = True  # 是否加入 a
                # 如果 st 有資料、 st 最後一項是正的且 a 是負的，發生碰撞
                while st and st[-1] > 0 and a < 0:
                    # a 量值較大，st 最後一項被撞掉
                    if abs(a) > st[-1]:
                        st.pop()
                    # 一樣大，st 最後一項及 a 同時被撞掉
                    elif abs(a) == st[-1]:
                        st.pop()
                        add_new = False
                        break
                    # a 較小，a 被撞掉
                    else:
                        add_new = False
                        break
                # 加入 a
                if add_new: st.append(a)
        return st

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 21.50 MB, beats 97.22%.

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        vector<int> st;
        for(int a : asteroids) {
            // 如果 st 是空的、st 最後一項是負的或者st 最後一項是正的且 a 是正的，不會碰撞，直接加入 a
            if (st.empty() || st.back() < 0 || (st.back() > 0 && a > 0)) {
                st.push_back(a);
            } else {  // 發生碰撞
                bool add_new = true;  // 是否加入 a
                // 如果 st 有資料、 st 最後一項是正的且 a 是負的，發生碰撞
                while(!st.empty() && st.back() > 0 && a < 0) {
                    // a 量值較大，st 最後一項被撞掉
                    if (abs(a) > st.back()) {
                        st.pop_back();
                    } else if (abs(a) == st.back()) {
                        // 一樣大，st 最後一項及 a 同時被撞掉
                    
                        st.pop_back();
                        add_new = false;
                        break;
                    } else {  // a 較小，a 被撞掉
                        add_new = false;
                        break;
                    }
                }
                // 加入 a
                if (add_new) st.push_back(a);
            }
        }
        return st;
    }
};