Day 12 of 30-Day LeetCode Challenge

We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

• If x == y, both stones are totally destroyed;
• If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)

class Solution {
public:
int lastStoneWeight(vector<int>& stones) {

//Use binary heap
priority_queue<int> q;
for(auto x:stones){
q.push(x);
}

while(q.size()>1){
int a = q.top();
q.pop();
int b = q.top();
q.pop();
int diff = a-b;
if(diff>=0) q.push(diff);
cout<<a<<”, “<<b<<”, “<<diff<<endl;
}
return q.top();
}
};