You are given an array of stone weights. On each turn, choose the two heaviest stones and smash them together.
If the stones are equal, both are destroyed. Otherwise the smaller stone is destroyed and the larger stone is reduced by the smaller stone's weight. Return the weight of the last remaining stone, or 0 if none remain.
Use a heap when the next smallest or largest candidate matters more than the full sorted order. Keep stale or no-longer-valid entries from affecting the answer.
Examples
Input: stones = [2,7,4,1,8,1] Output: 1
Input: stones = [1] Output: 1
Constraints
- 1 <= stones.length <= 30
- 1 <= stones[i] <= 1,000