【优先级队列】Leetcode 最后一块石头的重量

题目讲解

1046. 最后一块石头的重量

算法讲解

根据题目的意思，为了寻找到本次数组中的最大的两个值，我们需要使用一个数据结构：堆，使用大堆，每一次出两个数据，这两个数据就是当前数组中的两个最大值，之后在按照题目的意思进行模拟即可

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        // 建立一个大堆-》降序
        priority_queue<int, vector<int>, less<int>> pq(stones.begin(),stones.end());
        while (pq.size() > 1) {
            int first_num = pq.top();
            pq.pop();
            int second_num = pq.top();
            pq.pop();
            if (first_num < second_num) {
                second_num -= first_num;
                pq.push(second_num);
            }
            if (first_num > second_num) {
                first_num -= second_num;
                pq.push(first_num);
            }
        }
        if(!pq.empty())return pq.top();
        return 0;
    }
};