leetcode 1046. Last Stone Weight （最后剩余石子的重量）

题目要求

有一些石子，每个石子都有一个重量，每次我们选择两个最重的石子x,y。如果这两个石子重量相同，那么同时被销毁，否则重量小的被销毁，较重的石子重量变为（|x-y|）

解题思路

有一点贪心的策略，每次找最大的两个数，然后比较即可。在这里，我们可以用堆（heap）来实现，通过借用 priority_queue来实现堆。有了这个思想代码能很快的写出来。

这里还可以 使用multiset来实现，multiset是由平衡二叉搜索树来实现的，刚好也符合题目的要求，用到了prev,erase等操作和优先级队列思想类似，大家可以通过代码了解一下。

主要代码c++

//priority_queue
class Solution {
    
public:int lastStoneWeight(vector<int>& stones) {
    priority_queue<int> pq (stones.begin(), stones.end());while(pq.size()>1){
    int y = pq.top();pq.pop();int x = pq.top();pq.pop();if(y>x) pq.push(y-x);}return pq.empty() ? 0 : pq.top();}
};

// multiset 方法
class Solution {
    
public:int lastStoneWeight(vector<int>& stones) {
    multiset<int>s(stones.begin(), stones.end());while(s.size()>1){
    auto w1 = *prev(s.end()); // 获取最后一个位置的值s.erase(prev(s.end()));   // 删除最后一个位置元素auto w2 = *prev(s.end());s.erase(prev(s.end()));if(abs(w1-w2)>0) s.insert(abs(w1-w2));} return s.empty() ? 0: *s.begin();}
};