You have a collection of stones with positive integer weights. Each turn, choose the two heaviest stones and smash them. If they have different weights, the lighter one is destroyed and the heavier one loses weight equal to the lighter. Return the weight of the last remaining stone, or 0 if none remain.
Java
Last Stone Weight
You have a collection of stones with positive integer weights. Each turn, choose the two heaviest stones and smash them. If they have different weights, the lighter one is destroyed and the heavier one loses weight equal to the lighter. Return the weight of the last remaining stone, or 0 if none remain.
Example 1:
Input: [2,7,4,1,8,1]
Output: 1
Input
arr =[2,7,4,1,8,1]
Build max heap from stones: [2, 7, 4, 1, 8, 1]
Max Heap (heaviest on top)
8
7
4
2
1
1
Algorithm Insight:
Use a max heap to always get the two heaviest stones efficiently. Smash them and push the difference back if non-zero.