Last stone weight

Repeatedly smash the two heaviest stones together using a max-heap, until at most one stone remains.

The idea

A max-heap always exposes the two heaviest stones at the front. Smash them together: the lighter one is destroyed, and the difference (if any) goes back on the heap as a new, usually lighter, stone. Repeat until at most one stone is left.

Code

public static int LastStoneWeight(int[] stones) {
    var heap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a)); // max-heap
    foreach (int s in stones) heap.Enqueue(s, s);
    while (heap.Count > 1) {
        int y = heap.Dequeue();
        int x = heap.Dequeue();
        if (y != x) heap.Enqueue(y - x, y - x);
    }
    return heap.Count == 1 ? heap.Peek() : 0;
}

Tips

• Pushing the leftover stone back and letting the heap re-sort is simpler than tracking positions by hand.
• If the two heaviest stones are equal, both vanish — push nothing back.

In the .NET library

This greedy "always combine the two biggest" shape also shows up in Huffman coding, where you repeatedly merge the two least-frequent symbols instead of the two heaviest stones.