1046-Last-Stone-Weight.cpp

/*
 Given array of stones to smash, return smallest possible weight of last stone
 If x == y both stones destroyed, if x != y stone x destroyed, stone y = y - x
 Ex. stones = [2,7,4,1,8,1] -> 1, [2,4,1,1,1], [2,1,1,1], [1,1,1], [1]

 Max heap, pop 2 biggest, push back difference until no more 2 elements left

 Time: O(n log n)
 Space: O(n)
*/

classSolution {
public:
intlastStoneWeight(vector<int>& stones) {
 priority_queue<int> pq;
for (int i = 0; i < stones.size(); i++) {
 pq.push(stones[i]);
 }

while (pq.size() > 1) {
int y = pq.top();
 pq.pop();
int x = pq.top();
 pq.pop();
if (y > x) {
 pq.push(y - x);
 }
 }

if (pq.empty()) {
return0;
 }
return pq.top();
 }
};