題目網址：https://leetcode.cn/problems/last-stone-weight/

題意：給一整數 array stones, 其中 stones[i] 代表第 i 塊石頭的重量。

每一回合取出最重的兩塊石頭, 並將其互相撞擊。假設石頭的重量分別為 x、y, 且 x ≤ y。則撞擊後的可能結果如下：

  • 若 x == y, 則兩塊石頭都將完全粉碎
  • 若 x != y, 則重量為 x 的石頭將完全粉碎, 而重量為 y 的石頭之新重量為 y - x

最後, 頂多剩下一塊石頭。若沒有石頭剩下, 則返回 0; 否則, 返回該石頭的重量。

Solution：

想法：利用 Heap, 先將所有的元素 push 到 max heap pq 中, 再從 pq 中兩兩取出元素做運算

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq; // max heap
        for (const auto& stone : stones) {
            pq.emplace(stone);
        }

        while (pq.size() > 1) {
            const auto y = pq.top();
            pq.pop();

            const auto x = getTop(pq);
            pq.pop();

            pq.emplace(y - x);
        }

        return pq.top();
    }
};
  • time：$O(n \cdot log(n))$ ➔ 將所有的 stone push 到 pq 中、將所有 stone 取出來做運算, 其中 n 為 stone 的個數
  • space：$O(n)$ ➔ pq 中的元素個數不超過 n