557. Last Pebble
A river game starts with a pile of pebbles whose weights are given in the array stones. In every round you take the two heaviest pebbles, with weights x >= y, and smash them together.
If x == y both pebbles vanish. Otherwise the lighter one vanishes and the heavier one is worn down to weight x - y and goes back into the pile. The game ends when at most one pebble is left.
Return the weight of the last remaining pebble, or 0 if no pebble remains. The final answer does not depend on how equally heavy pebbles are chosen. Aim for O(n log n) time and O(n) space.
Example 1
- Input:
- stones = [12,7,4,4,1]
- Output:
- 2
- Explanation:
Smash 12 and 7 to get 5; then 5 and 4 to get 1; then 4 and 1 to get 3; then 3 and 1 to get 2, so one pebble of weight 2 remains.
Example 2
- Input:
- stones = [5,5]
- Output:
- 0
- Explanation:
The two equal pebbles destroy each other, leaving nothing, so the answer is 0.
Example 3
- Input:
- stones = [8]
- Output:
- 8
- Explanation:
A single pebble is never smashed, so its weight 8 is returned.
Constraints
- 1 ≤
stones.length≤ 105 - 1 ≤
stones[i]≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n log n)
- Space
- O(n)