Last Stone Weight
Easy · heap
You have a pile of stones, and stones[i] is the weight of the i-th stone. The game is played in rounds. In each round, take the two heaviest stones and smash them together:
- If they weigh the same, both stones are destroyed.
- Otherwise the lighter one is destroyed, and the heavier one stays in the pile with a new weight equal to the difference of the two.
The game ends when at most one stone is left. Return the weight of that last stone, or 0 if no stone is left. When several stones share a weight, it does not matter which of them you pick.
Examples
Example 1
Input: stones = [2, 7, 4, 1, 8, 1]
Output: 1
Smash 8 and 7 to get 1, then 4 and 2 to get 2, then 2 and 1 to get 1. The pile is now 1, 1, 1: smash two of them away and the last 1 remains.
Example 2
Input: stones = [3, 3]
Output: 0
The two stones weigh the same, so both are destroyed and nothing is left.
Example 3
Input: stones = [9]
Output: 9
A single stone is never smashed.
Constraints
- 1 <= len(stones) <= 5000
- 1 <= stones[i] <= 10^6