📘 題目敘述
給定一個整數陣列 stones，其中 stones[i] 表示第 i 顆石頭的重量。
現在要進行一個遊戲。每一回合都會選出目前最重的兩顆石頭互相撞擊。
假設這兩顆石頭的重量分別是 x 和 y，且 x <= y，撞擊後會有兩種情況：
- 如果
x == y，那這兩顆石頭都會被摧毀 - 如果
x != y，那重量為x的石頭會被摧毀，而重量為y的石頭會變成新重量y - x
最後最多只會剩下一顆石頭。
請回傳最後剩下那顆石頭的重量。
如果一顆都不剩，回傳 0。
條件限制
1 <= stones.length <= 301 <= stones[i] <= 1000
🧠 解題思路
我這題的想法就是直接模擬題目過程，然後用 priority_queue 快速拿到目前最重的兩顆石頭。
因為每一回合都要找「最大的兩個」，這種操作很適合用 max heap。
在 C++ 裡，priority_queue<int> 預設就是最大堆，所以我可以把所有石頭先丟進去。
之後每次：
- 先拿出最重的兩顆
- 看它們相撞後會不會留下新石頭
- 如果有，就把新石頭再丟回 heap
一直做到 heap 裡剩 0 顆或 1 顆石頭為止。
所有變數
pq：max heap，裡面放目前所有還存在的石頭重量x：這一回合取出的其中一顆石頭重量y：這一回合取出的另一顆石頭重量
🪜 主要流程步驟
1. 先把所有石頭放進 priority_queue
我先建立一個 priority_queue<int>，讓它幫我維護目前所有石頭中的最大值。
然後把 stones 裡的每顆石頭都放進去：
這樣之後每次都能直接從 pq.top() 拿到目前最重的石頭。
2. 每次取出最重的兩顆石頭來撞
只要 pq.size() > 1，就代表目前至少還有兩顆石頭可以互撞。
所以我在迴圈裡每次都做這件事：
- 先取出第一顆最重的石頭
x - 再取出第二顆最重的石頭
y
因為 priority_queue 每次都會把目前最大的值放在頂端，所以這樣拿到的就是當前最重的兩顆石頭。
3. 如果兩顆一樣重，就直接消失
如果 x - y == 0，代表兩顆石頭重量一樣。
按照題目規則，這兩顆都會被摧毀，所以這回合不用再做其他事情，直接進下一輪就可以。
也就是這回合拿出來的兩顆石頭都不會再放回去。
4. 如果兩顆不一樣重，就把差值丟回去
如果兩顆石頭重量不同，那麼比較輕的那顆會消失，比較重的那顆則會變成它們重量差。
所以我就把：
abs(x - y)
再放回 pq 裡
因為這顆新石頭之後還可能再和其他石頭互撞，所以要重新放回 heap 裡，讓後面的回合繼續使用。
5. 最後看 heap 裡還有沒有石頭
當迴圈結束時，只會有兩種情況：
pq是空的，表示所有石頭都撞完消失了pq裡還剩一顆，表示那就是最後答案
所以最後我先判斷：
if (pq.empty()) {
return 0;
}
如果是空的，就回傳 0。
否則直接回傳 pq.top()，也就是最後剩下的那顆石頭重量。
⏱️ 複雜度
設 n = stones.length。
時間複雜度：
O(n log n)
一開始把石頭放進 heap，後面每回合都會做 pop 和 push，而 heap 操作是O(log n)。空間複雜度：
O(n)
priority_queue需要存目前所有石頭。
💻 程式碼實作
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> pq;
for (int i : stones) {
pq.push(i);
}
while (pq.size() > 1) {
int x = pq.top();
pq.pop();
int y = pq.top();
pq.pop();
if ((x - y) == 0) {
continue;
}
pq.push(abs(x - y));
}
if (pq.empty()) {
return 0;
}
return pq.top();
}
};
🔗 題目連結
https://leetcode.com/problems/last-stone-weight/