326. Last Stone Weight

Each turn needs the two heaviest stones. A max-heap gives them in O(log n) and lets us push the smashed remainder back just as cheaply.

Why a heap?

Every turn we need the two largest stones, and after smashing we may insert a new stone. Repeatedly scanning for the max is O(n) per turn; a max-heap gives the max in O(log n) and reinserts in O(log n).

Python's heapq is a min-heap, so we store negated weights to simulate a max-heap.

Walk-through

1. Build a max-heap of all stone weights.
2. While more than one stone remains:
   • Pop the two heaviest, y then x (so x <= y).
   • If x != y, push y - x back onto the heap.
   • If x == y, both are gone.
3. Return the single remaining stone, or 0 if the heap is empty.

Worked example

stones = [2,7,4,1,8,1] → max-heap top is 8.

• Smash 8 & 7 → push 1. Heap: [4,2,1,1,1]
• Smash 4 & 2 → push 2. Heap: [2,1,1,1]
• Smash 2 & 1 → push 1. Heap: [1,1,1]
• Smash 1 & 1 → equal, both gone. Heap: [1]
• One stone left → return 1.

Complexity

• Time: O(n log n) — up to n smashes, each with O(log n) heap operations.
• Space: O(n) — the heap.

import java.util.PriorityQueue;
import java.util.Collections;

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        for (int s : stones) {
            heap.offer(s);
        }
        while (heap.size() > 1) {
            int y = heap.poll();   // heaviest
            int x = heap.poll();   // second heaviest (x <= y)
            if (y != x) {
                heap.offer(y - x);
            }
        }
        return heap.isEmpty() ? 0 : heap.peek();
    }
}