1046. 最後一塊石頭的重量

思路

每次拿出最大的兩顆石頭相撞，並將結果重新放回石頭堆中。
這類「過程中數組會變化」但是又要求有序的題目，大都可以往堆的方向去想。

程式碼

堆

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq;
        for(int stone : stones) {
            pq.push(stone);
        }
        while(pq.size() > 1) {
            int y = pq.top(); pq.pop(); // 取出兩顆石頭
            int x = pq.top(); pq.pop();
            if(x < y) { // 石頭不相等，相撞
                pq.push(y - x);
            }
        }
        return pq.empty() ? 0 : pq.top();
    }
};

複雜度分析

• 時間複雜度：$O(n\log{n})$
• 空間複雜度：$O(n)$