題目描述:給定一個整數陣列 stones,其中每個元素代表一塊石頭的重量。每一回合,選出最重的兩塊石頭並將它們相撞。若兩者重量相等則兩塊都消失;若不等,較輕的那塊消失,較重的那塊剩下重量差值。重複此過程直到最多剩一塊石頭,回傳其重量(若無石頭則回傳 0)。
解題思路:這題的核心操作是「反覆取出最大的兩個元素、處理後再放回」,天然對應**最大堆(max-heap)**資料結構。C++ STL 的 priority_queue 預設即為最大堆,每次 top() 取出最大值的時間複雜度為 O(log n)。
演算法步驟:
y(最大)和 x(次大)。y != x,將差值 y - x 推回堆中;若相等則什麼都不做(兩塊都消失)。關鍵直覺:由於每次操作至少消滅一塊石頭(兩塊相等消滅兩塊,不等消滅一塊),最多執行 n-1 次操作即可結束。
時間複雜度:O(n log n) — 建堆需要 O(n),每次操作(pop 兩次、最多 push 一次)需要 O(log n),最多執行 n-1 次操作,總計 O(n log n)。
空間複雜度:O(n) — 最大堆在最壞情況下儲存所有 n 塊石頭。
1. Initialize a max-heap with all stone weights. 2. While the heap has more than 1 element: a. Pop the largest stone y. b. Pop the second largest stone x. c. If y != x, push (y - x) back into the heap. 3. If the heap is empty, return 0; otherwise return heap.top().
排序模擬 O(n² log n):每回合對陣列排序,取出最後兩個元素比較後放回,再排序。邏輯簡單但效率遠低於堆,不建議在競賽中使用。
多重集合 multiset O(n log n):使用 C++ multiset 也能達到相同效果——每次從尾端取出最大兩個元素、刪除後視情況插入差值。multiset 維持有序,操作同為 O(log n),但常數因子略大於 priority_queue,且需要反向迭代器,程式碼稍複雜。