题目讲解
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;
}
};