# 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();

}

};