這題我們要透過模擬砸石頭的過程，計算最後剩下的石頭重量。

題目：
給定一組石頭，每塊石頭有其重量。我們每次選出兩塊最重的石頭 x 和 y（x >= y），並按以下規則進行處理：

• 如果 x == y，則兩塊石頭完全粉碎，不留任何碎片。
• 如果 x > y，則 x 和 y 會互相砸碎，最後只剩下 x - y 的重量。

這樣重複進行直到剩下一塊或沒有石頭，回傳最後剩下的石頭重量。如果沒有石頭剩下，則回傳 0。

範例：

輸入: stones = [2,7,4,1,8,1]
輸出: 1

輸入: stones = [1]
輸出: 1

解題思路

迴圈每次將 stones 排序，再依序從後面取出兩個，即最大的兩個，然後進行砸碎操作，

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        while (stones.size() > 1) {
            sort(stones.begin(), stones.end());

            int stone1 = stones.back();
            stones.pop_back();
            int stone2 = stones.back();
            stones.pop_back();

            if (stone1 > stone2) {
                stones.push_back(stone1 - stone2);
            }
        }
        return stones.size() == 1 ? stones[0] : 0;
    }
};

時間複雜度：O(n^2 log n)(每次排序需 O(n log n)，加上每輪運算移除1或2個元素，最差需要O(n)輪)
空間複雜度：O(1)，只需要額外常數個變數儲存

既然 topic 有 Heap (Priority Queue)，那就用 Priority Queue 來練習解這題，
這樣每次迴圈就可以免去排序，因為 Priority Queue 自己會按優先順序排，記得 priority_queue 要用 top() 而不是 front()，

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> queue; // 預設由大到小
        for (auto i : stones)
            queue.push(i);

        while (queue.size() > 1) {
            int stone1 = queue.top();
            queue.pop();
            int stone2 = queue.top();
            queue.pop();

            if (stone1 > stone2) {
                queue.push(stone1 - stone2);
            }
        }
        return queue.size() == 1 ? queue.top() : 0;
    }
};

時間複雜度：O(n log n)(Priority Queue 插入時間複雜度 O(log n)，加上每輪運算移除1或2個元素，最差需要O(n)輪)
空間複雜度：O(n)，需要 priority_queue 來存放 n 個 stones

參考：
#1046. Last Stone Weight