Last Stone Weight

easy

You are given an array of integers stones where stones[i] is the weight of the i-th stone.

We are playing a game with the stones. On each turn, we choose the two heaviest stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y:

If x == y, both stones are destroyed.
If x != y, the stone of weight x is destroyed and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left. Return the weight of the last remaining stone, or 0 if there are no stones left.

Test Cases

Copy an input into the main harness and Run to verify

Input

stones = [2,7,4,1,8,1]

Expected Output

1

Explanation: Smashing 8 and 7 leaves 1; then 4 and 2 leave 2; then 2 and 1 leave 1; then 1 and 1 destroy each other, leaving 1.

Input

stones = [1]

Expected Output

1

Constraints

1 <= stones.length <= 30
1 <= stones[i] <= 1000

Hints

Hint 1 — click to reveal

You repeatedly need the two largest values, and the result goes back into the pool.

Hint 2 — click to reveal

That is exactly what a max-heap is for.

Java Compiler