LeetCode 解題筆記：2126. Destroying Asteroids

作者：王一哲
日期：2026年5月31日


LeetCode 題目連結：2126. Destroying Asteroids

解題想法

中級難度的題目。我看到題目時最直接的想法，是先將小行星的質量由小到大排序，再依序讀取小行星的質量 a，如果行星質量 mass 大於等於 a，將 mass 加上 a；反之回傳 False。如果測試完所有的小行星質量都不會回傳 False，最後則回傳 True。

後來又想到，既然每次都要取出所有小行星質量之中的最小值，應該也可以用最小優先佇列解題。先將所有的小行星質量存入最小優先佇列 pq 之中，再用 while 迴圈取出 pq 之中的最小值與 mass 比較，但這樣寫多了掃過所有小行星質量花費的時間，反而比直接排序慢。

那如果稍微修改一下寫法，先掃過所有小行星質量一次，如果行星質量 mass 大於等於這個小行星質量 a，將 mass 加上 a；反之將 a 加入最小優先佇列 pq 之中，時間複雜度 $O(n)$。最後再用 while 迴圈取出 pq 之中的最小值與 mass 比較，pq 插入、刪除資料的時間複雜度為 $O(log n)$，由於 pq 之中的資料數量一定小於測資給的小行星數量，速度比前兩種寫法還快。

Python 程式碼

排序。Runtime: 71 ms, beats 73.70%. Memory: 34.01 MB, beats 30.13%.

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        for a in sorted(asteroids):
            if mass >= a:
                mass += a
            else:
                return False
        return True

heapq。Runtime: 269 ms, beats 5.37%. Memory: 30.22 MB, beats 93.86%.

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        heapq.heapify(asteroids)
        while asteroids:
            a = heapq.heappop(asteroids)
            if mass >= a:
                mass += a
            else:
                return False
        return True

只存部分資料到 heapq 之中。Runtime: 62 ms, beats 95.20%. Memory: 33.66 MB, beats 90.21%.

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        pq = []
        for a in asteroids:
            if mass >= a:
                mass += a
            else:
                heapq.heappush(pq, a)
        while pq:
            a = heapq.heappop(pq)
            if mass >= a:
                mass += a
            else:
                return False
        return True

C++ 程式碼

排序。Runtime: 40 ms, beats 17.08%. Memory: 106.76 MB, beats 48.03%.

class Solution {
public:
    bool asteroidsDestroyed(int mass, vector<int>& asteroids) {
        sort(asteroids.begin(), asteroids.end());
        long long total = mass;
        for(int a : asteroids) {
            if (total >= a) {
                total += a;
            } else {
                return false;
            }
        }
        return true;
    }
};

priority_queue。Runtime: 130 ms, beats 5.84%. Memory: 117.50 MB, beats 5.11%.

class Solution {
public:
    bool asteroidsDestroyed(int mass, vector<int>& asteroids) {
        sort(asteroids.begin(), asteroids.end());
        long long total = mass;
        priority_queue<int, vector<int>, greater<int>> pq;
        for(int a : asteroids) pq.push(a);
        while(!pq.empty()) {
            int a = pq.top();
            pq.pop();
            if (total >= a) {
                total += a;
            } else {
                return false;
            }
        }
        return true;
    }
};

只存部分資料到 priority_queue 之中。Runtime: 27 ms, beats 84.23%. Memory: 107.38 MB, beats 8.18%.

class Solution {
public:
    bool asteroidsDestroyed(int mass, vector<int>& asteroids) {
        sort(asteroids.begin(), asteroids.end());
        long long total = mass;
        priority_queue<int, vector<int>, greater<int>> pq;
        for(int a : asteroids) {
            if (total >= a) {
                total += a;
            } else {
                pq.push(a);
            }
        }
        while(!pq.empty()) {
            int a = pq.top();
            pq.pop();
            if (total >= a) {
                total += a;
            } else {
                return false;
            }
        }
        return true;
    }
};