Last Stone Weight
Easy· max-heap· simulation
Problem
Each turn, take the two heaviest stones and smash them together. If they weigh the same both are destroyed; otherwise the lighter is destroyed and the heavier loses that much weight. Return the weight of the last stone left, or 0 if none remain.
Examples
Input: stones = [2,7,4,1,8,1]
Output: 1
8 vs 7 leaves 1, then 4 vs 2 leaves 2, then 2 vs 1 leaves 1, then 1 vs 1 leaves nothing, leaving a single 1.
Input: stones = [5,5]
Output: 0
Constraints
- • 1 <= stones.length <= 30
- • 1 <= stones[i] <= 1000
Hints & approach
Hint 1
You repeatedly need the two largest values from a changing collection.
Hint 2
A max-heap gives the largest in O(log n).
Approachtry the hints first
Load all weights into a max-heap (in languages with only a min-heap, store negatives). While more than one stone remains, pop the two largest; if they differ, push their difference back. When the loop ends, return the remaining stone or 0 if the heap is empty. Each round removes at least one stone, so there are at most n rounds.
Time O(n log n) · Space O(n)