Last Stone Weight
EasyHeap
You are given an array stones where stones[i] is the positive weight of the i-th stone.
Repeat the following step while at least two stones remain:
- Take the two heaviest stones, with weights
x <= y. - Smash them together:
- If
x == y, both stones are destroyed. - If
x < y, the lighter stone is destroyed and the heavier one survives with new weighty - x. It goes back into the pile and can be chosen again.
When fewer than two stones remain, return the weight of the last stone, or 0 if none are left.
Example 1
- Input:
- stones = [3, 8, 5, 2]
- Output:
- 2
- Explanation
- Smash 8 and 5, leaving a 3:
[3, 3, 2]. Smash the two 3s, which destroys both:[2]. One stone is left, weighing 2.
Example 2
- Input:
- stones = [6, 6, 4, 4]
- Output:
- 0
- Explanation
- The two 6s destroy each other, then the two 4s do the same, so no stones remain.
Example 3
- Input:
- stones = [10, 4, 3]
- Output:
- 3
- Explanation
- 10 and 4 leave a 6:
[6, 3]. Then 6 and 3 leave a 3, which is the last stone.
Constraints
1 <= stones.length <= 301 <= stones[i] <= 1000