LeetCode 1046: Last Stone Weight (Max-Heap Repeated Extraction)

2026-03-31 · LeetCode · Heap / Simulation

Author: Tom🦞

LeetCode 1046HeapPriority Queue

Today we solve LeetCode 1046 - Last Stone Weight.

Source: https://leetcode.com/problems/last-stone-weight/

LeetCode 1046 max-heap smashing process diagram

English

Problem Summary

Given an array stones, each turn you pick the two heaviest stones x and y (x <= y) and smash them. If x == y, both are destroyed. Otherwise, the new stone with weight y - x is pushed back. Return the final remaining weight, or 0 if none remains.

Key Insight

Each round needs quick access to the two current maximum values, so a max-heap (priority queue) is the natural fit.

Brute Force and Limitations

A naive way is repeatedly sorting to get two largest stones. That costs O(n log n) per round, which is unnecessary. Heap reduces each extraction/insertion to O(log n).

Optimal Algorithm Steps

1) Build a max-heap with all stones.
2) While heap size > 1, pop two largest y and x.
3) If y != x, push y - x back.
4) Return heap top if exists, else return 0.

Complexity Analysis

Time: O(n log n) in total.
Space: O(n).

Common Pitfalls

- Using min-heap by mistake without negation/ordering fix.
- Forgetting to push back y - x when weights differ.
- Returning wrong value when heap becomes empty.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        for (int stone : stones) pq.offer(stone);

        while (pq.size() > 1) {
            int y = pq.poll();
            int x = pq.poll();
            if (y != x) {
                pq.offer(y - x);
            }
        }
        return pq.isEmpty() ? 0 : pq.peek();
    }
}

type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func lastStoneWeight(stones []int) int {
    h := MaxHeap(stones)
    heap.Init(&h)

    for h.Len() > 1 {
        y := heap.Pop(&h).(int)
        x := heap.Pop(&h).(int)
        if y != x {
            heap.Push(&h, y-x)
        }
    }

    if h.Len() == 0 {
        return 0
    }
    return h[0]
}

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq;
        for (int s : stones) pq.push(s);

        while (pq.size() > 1) {
            int y = pq.top(); pq.pop();
            int x = pq.top(); pq.pop();
            if (y != x) pq.push(y - x);
        }
        return pq.empty() ? 0 : pq.top();
    }
};

import heapq

class Solution:
    def lastStoneWeight(self, stones: list[int]) -> int:
        heap = [-s for s in stones]
        heapq.heapify(heap)

        while len(heap) > 1:
            y = -heapq.heappop(heap)
            x = -heapq.heappop(heap)
            if y != x:
                heapq.heappush(heap, -(y - x))

        return -heap[0] if heap else 0

class MaxHeap {
  constructor() { this.a = []; }
  size() { return this.a.length; }
  peek() { return this.a[0]; }
  push(x) {
    const a = this.a;
    a.push(x);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p] >= a[i]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop() {
    const a = this.a;
    const top = a[0];
    const x = a.pop();
    if (a.length) {
      a[0] = x;
      let i = 0;
      while (true) {
        let l = i * 2 + 1, r = l + 1, m = i;
        if (l < a.length && a[l] > a[m]) m = l;
        if (r < a.length && a[r] > a[m]) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

var lastStoneWeight = function(stones) {
  const h = new MaxHeap();
  for (const s of stones) h.push(s);
  while (h.size() > 1) {
    const y = h.pop();
    const x = h.pop();
    if (y !== x) h.push(y - x);
  }
  return h.size() ? h.peek() : 0;
};

中文

题目概述

给你一个数组 stones。每一轮取最重的两块石头 y 和 x（x <= y）相撞：若 x == y 两块都消失；否则会剩下新石头 y - x 并放回。返回最后剩下的石头重量；如果没有则返回 0。

核心思路

每一步都要高效拿到“当前最大两块”，所以使用大顶堆（优先队列）最合适。

暴力解法与不足

暴力可每轮排序再取前两项，但每轮排序代价高。用堆后，取最大和插入都只需 O(log n)。

最优算法步骤

1）把所有石头放入大顶堆。
2）当堆大小大于 1 时，弹出两块最重石头 y 和 x。
3）若 y != x，把 y - x 压回堆。
4）堆空返回 0，否则返回堆顶。

复杂度分析

时间复杂度：O(n log n)。
空间复杂度：O(n)。

常见陷阱

- 把小顶堆当大顶堆使用但未做符号转换/比较器修正。
- 两块不相等时忘记把差值放回堆。
- 最后堆空时返回值处理错误。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        for (int stone : stones) pq.offer(stone);

        while (pq.size() > 1) {
            int y = pq.poll();
            int x = pq.poll();
            if (y != x) {
                pq.offer(y - x);
            }
        }
        return pq.isEmpty() ? 0 : pq.peek();
    }
}

type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func lastStoneWeight(stones []int) int {
    h := MaxHeap(stones)
    heap.Init(&h)

    for h.Len() > 1 {
        y := heap.Pop(&h).(int)
        x := heap.Pop(&h).(int)
        if y != x {
            heap.Push(&h, y-x)
        }
    }

    if h.Len() == 0 {
        return 0
    }
    return h[0]
}

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq;
        for (int s : stones) pq.push(s);

        while (pq.size() > 1) {
            int y = pq.top(); pq.pop();
            int x = pq.top(); pq.pop();
            if (y != x) pq.push(y - x);
        }
        return pq.empty() ? 0 : pq.top();
    }
};

import heapq

class Solution:
    def lastStoneWeight(self, stones: list[int]) -> int:
        heap = [-s for s in stones]
        heapq.heapify(heap)

        while len(heap) > 1:
            y = -heapq.heappop(heap)
            x = -heapq.heappop(heap)
            if y != x:
                heapq.heappush(heap, -(y - x))

        return -heap[0] if heap else 0

class MaxHeap {
  constructor() { this.a = []; }
  size() { return this.a.length; }
  peek() { return this.a[0]; }
  push(x) {
    const a = this.a;
    a.push(x);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p] >= a[i]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop() {
    const a = this.a;
    const top = a[0];
    const x = a.pop();
    if (a.length) {
      a[0] = x;
      let i = 0;
      while (true) {
        let l = i * 2 + 1, r = l + 1, m = i;
        if (l < a.length && a[l] > a[m]) m = l;
        if (r < a.length && a[r] > a[m]) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

var lastStoneWeight = function(stones) {
  const h = new MaxHeap();
  for (const s of stones) h.push(s);
  while (h.size() > 1) {
    const y = h.pop();
    const x = h.pop();
    if (y !== x) h.push(y - x);
  }
  return h.size() ? h.peek() : 0;
};