### Problem statement

You are given an array of integers `stones`

where `stones[i]`

is the weight of the `i-th`

stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights `x`

and `y`

with `x <= y`

. The result of this smash is:

If

`x == y`

, both stones are destroyed, andIf

`x != y`

, the stone of weight`x`

is destroyed, and the stone of weight`y`

has new weight`y - x`

.

At the end of the game, there is at most one stone left.

Return the smallest possible weight of the left stone. If there are no stones left, return `0`

.

#### Example 1

```
Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation:
We combine 7 and 8 to get 1, so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2, so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1, so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0, so the array converts to [1] then that's the value of the last stone.
```

#### Example 2

```
Input: stones = [1]
Output: 1
```

#### Constraints

`1 <= stones.length <= 30`

.`1 <= stones[i] <= 1000`

.

### Solution: Keeping the heaviest stones on top

The only things you want at any time are the two heaviest stones. One way of keeping this condition is by using `std::priority_queue`

.

#### Code

```
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> q(stones.begin(), stones.end());
while (q.size() >= 2) {
int y = q.top();
q.pop();
int x = q.top();
q.pop();
if (y != x) {
q.push(y - x);
}
}
return q.empty() ? 0 : q.top();
}
int main() {
vector<int> stones{2,7,4,1,8,1};
cout << lastStoneWeight(stones) << endl;
stones = {1};
cout << lastStoneWeight(stones) << endl;
}
```

```
Output:
1
1
```

#### Complexity

Runtime: worst case

`O(NlogN)`

, on average`O(N)`

, where`N = stones.length`

.Extra space:

`O(N)`

.

### References

*Thanks for reading. Feel free to share your thought about my content and check out my* *FREE book “10 Classic Coding Challenges”**.*

### Did you find this article valuable?

Support **LeetSolve** by becoming a sponsor. Any amount is appreciated!