Heaps Simulating with a heap
414. Last Stone Weight
You are given an array stones, where stones[i] is the weight of the i-th stone. The stones are smashed
together, two at a time, in turns.
In each turn, the two heaviest stones are smashed together. Their weights are x and y, with x ≤ y. If
x == y, both stones are destroyed. Otherwise the stone of weight x is destroyed, and the other stone now weighs
y − x and goes back with the rest.
The turns go on until at most one stone is left. Return the weight of that stone, or 0 if no stone is left.
Example 1
Input: stones = [4, 9, 2, 7, 3]
1Explanation: 9 and 7 leave a stone of 2. Then 4 and 3 leave a stone of 1. The two stones of 2 destroy each other, and the stone of 1 is left.
Example 2
Input: stones = [5, 3, 8]
0Explanation: 8 and 5 leave a stone of 3. It meets the other stone of 3, and both are destroyed, so no stone is left.
Example 3
Input: stones = [1000000000]
1000000000Explanation: There is only one stone, so no turn happens.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ stones.length ≤ 1051 ≤ stones[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.