1.題目

1046. 最后一塊石頭的重量

- 如果 `x == y`，那么兩塊石頭都會被完全粉碎；- 如果 `x != y`，那么重量為 `x` 的石頭將會完全粉碎，而重量為 `y` 的石頭新重量為 `y-x`。

**輸入：**[2,7,4,1,8,1]
**輸出：**1
**解釋：**
先選出 7 和 8，得到 1，所以數組轉換為 [2,4,1,1,1]，
再選出 2 和 4，得到 2，所以數組轉換為 [2,1,1,1]，
接著是 2 和 1，得到 1，所以數組轉換為 [1,1,1]，
最后選出 1 和 1，得到 0，最終數組轉換為 [1]，這就是最后剩下那塊石頭的重量。

2.思路

優先級隊列

priority_queue<int, vector<int>, greater<int>> minHeap;
創建小根堆，int是比較類型，vector<int>存儲元素底層容器類型，greater<int>是比較函數，小根堆必須寫
priority_queue<int> minHeap;
創建大根堆，int是比較類型，vector<int>存儲元素底層容器類型，可以不寫，less<int>是比較函數，大根堆可以不寫，下面這樣寫也可以
priority_queue<int, vector<int>, less<int>> minHeap;

push(const T& value)：向隊列中插入一個元素，插入后堆會自動調整以保持優先級順序。

pop()：刪除隊列中的堆頂元素（優先級最高的元素），堆會重新調整。

top()：返回隊列中的堆頂元素（優先級最高的元素），但不刪除它。

empty()：判斷隊列是否為空，如果為空返回 true，否則返回 false。

size()：返回隊列中元素的數量。

自定義類型比較：

#include <iostream>
#include <queue>
#include <vector>// 自定義結構體
struct Person {std::string name;int age;Person(const std::string& n, int a) : name(n), age(a) {}
};// 自定義比較函數，按年齡從大到小排序
//如果比較函數 comp(a, b) 返回 true 表示 a 的優先級低于 b，那么在堆中 b 會更靠近堆頂；反之，如果 comp(a, b) 返回 true 表示 a 的優先級高于 b，則 a 會更靠近堆頂。
struct ComparePerson {bool operator()(const Person& p1, const Person& p2) {return p1.age < p2.age;}
};int main() {// 創建一個存儲 Person 對象的大頂堆std::priority_queue<Person, std::vector<Person>, ComparePerson> personHeap;// 插入元素personHeap.push(Person("Alice", 25));personHeap.push(Person("Bob", 30));personHeap.push(Person("Charlie", 20));// 訪問堆頂元素（年齡最大的人）std::cout << "堆頂元素（年齡最大的人）: " << personHeap.top().name << ", 年齡: " << personHeap.top().age << std::endl;return 0;
}

3.代碼

#include <vector>
#include <queue>class Solution {
public:// 該函數用于計算最后剩下石頭的重量// 給定一個整數向量 stones 表示每塊石頭的重量，模擬石頭碰撞過程，返回最后剩下石頭的重量int lastStoneWeight(std::vector<int>& stones) {// 創建一個大頂堆優先隊列 q，用于存儲石頭的重量// 大頂堆會自動將元素按從大到小的順序排列，堆頂元素始終是最大的std::priority_queue<int> q;// 遍歷石頭重量向量 stonesfor (auto& e : stones) {// 將每塊石頭的重量壓入優先隊列 q 中q.push(e);}// 當優先隊列中石頭的數量大于 1 時，繼續進行石頭碰撞操作while (q.size() > 1) {// 取出優先隊列中最重的石頭的重量，存儲在變量 x 中int x = q.top();// 將最重的石頭從優先隊列中移除q.pop();// 取出此時優先隊列中最重的石頭的重量，存儲在變量 y 中int y = q.top();// 將這塊石頭從優先隊列中移除q.pop();// 如果 x 大于 y，說明兩塊石頭碰撞后會剩下重量為 x - y 的石頭if (x > y) {// 將碰撞后剩下的石頭重量壓入優先隊列中q.push(x - y);}// 如果 x 等于 y，兩塊石頭碰撞后都消失，不需要再做額外操作}// 判斷優先隊列是否為空if (q.empty()) {// 如果為空，說明所有石頭都在碰撞過程中消失了，返回 0return 0;} else {// 如果不為空，說明還剩下一塊石頭，返回該石頭的重量return q.top();}}
};