593. Last Stone Weight
You are given an array of positive integers stones, where stones[i] is the weight of one stone in a pile.
Repeat the following move until at most one stone is left: take the two heaviest stones, with weights x <= y, and smash them into each other.
- If
x == y, both stones shatter and nothing returns to the pile. - If
x < y, the lighter stone is destroyed and the heavier one shrinks to weighty - x, which goes back into the pile.
Return the weight of the one stone that survives, or 0 if the pile ends up empty.
Example 1:
Input: stones = [2, 7, 4, 1, 8, 1]
Output: 1
Explanation: Smash 8 and 7 → a stone of weight 1 returns, pile [2, 4, 1, 1, 1]. Smash 4 and 2 → 2 returns, pile [2, 1, 1, 1]. Smash 2 and 1 → 1 returns, pile [1, 1, 1]. Smash 1 and 1 → both shatter, pile [1]. One stone of weight 1 remains.
Example 2:
Input: stones = [3, 7, 2]
Output: 2
Explanation: Smash 7 and 3 → 4 returns, pile [4, 2]. Smash 4 and 2 → 2 returns, pile [2]. The survivor weighs 2.
Constraints:
- 1 ≤ stones.length ≤ 30
- 1 ≤ stones[i] ≤ 1000
Hints:
Each round only ever needs the two heaviest stones in the current pile. Which data structure hands you the maximum in O(log n) per operation, even as new weights keep arriving?
Push every weight into a max-heap. Pop twice, and if the two weights differ, push the difference back. Stop when the heap holds at most one element. In Python, heapq is a min-heap — store negated weights to flip it.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: stones = [2, 7, 4, 1, 8, 1]
Expected output: 1