LeetCode 1046. 最后一块石头的重量

2023-04-05 HGNULB 约 6 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 1046. 最后一块石头的重量

题意分析

一堆石头，每次挑出最重的两块相撞：重量相同则两块都粉碎；不同则轻的粉碎、重的剩下 y - x。重复到石头不超过一块，返回最后剩下那块的重量，没剩就返回 0。

这题的规则完全没有选择余地——每一轮撞哪两块是被题目钦定的（最重的两块），不需要做任何最优化决策。所以它不是贪心题也不是 DP 题，而是一道纯粹的模拟题，唯一的问题是：怎样高效地反复取出「当前最大的两个元素」，并把新产生的差值放回集合。

「反复取最大 + 动态插入新元素」这个访问模式是优先队列的教科书场景。注意集合是动态变化的：撞完产生的 y - x 会成为新石头参与后续比较，所以不能先排序然后一趟扫完——新元素的位置无法预知。

约束是 1 ≤ stones.length ≤ 30、1 ≤ stones[i] ≤ 1000，规模小到几乎怎么写都能过；但面试官问的是解法结构，不是能不能过。

边界有三处：只有一块石头时不发生任何碰撞，直接返回它；两块等重时全部粉碎，集合变空要返回 0；差值 y - x 可能为 0——此时不应该把 0 放回堆里，否则最后可能剩下一个「重量为 0 的石头」，虽然返回值恰好也是 0，但集合大小的语义就乱了（例如 [1, 1, 2] 会多绕一轮）。

解法：大顶堆模拟

核心思路

每轮都要从动态集合中删除最大的两块，并可能插入一块新石头。一次排序不够，因为新产生的差值还要重新参与大小比较；大顶堆正好支持这组操作。

把所有石头放入大顶堆。只要堆中至少有两块，就连续弹出 first 和 second，堆性质保证 first >= second。若二者不等，把正差 first - second 放回堆；相等时两块都消失，不放入 0。

不变量：每轮开始时，堆中的元素与当前尚未粉碎的石头一一对应，堆顶是其中最重的一块。一次循环严格执行题目规定的碰撞，并把结果恢复到堆中，所以不变量保持成立。每轮石头数至少减少 1，循环一定终止。

正确性：题目规定每轮必须选择当前最重的两块，没有其他决策。大顶堆弹出的前两个元素恰是这两块，更新规则也与碰撞规则一致。归纳到循环结束时，堆为空表示全部粉碎，堆中一个元素就是唯一剩余重量。

解题步骤

建立大顶堆并放入所有石头。Java 的 PriorityQueue 默认是小顶堆，需要逆序比较器；Go 在 Less 中使用 >。

当堆大小大于 1 时，弹出最大的两块。

若重量不同，将二者之差重新入堆；相同则不做任何插入。

循环结束后，空堆返回 0，否则返回唯一元素。

样例 [2,7,4,1,8,1] 的碰撞过程是 (8,7)->1、(4,2)->2、(2,1)->1、(1,1)->0，最后剩下 1。

边界上，[1] 不进入循环并直接返回 1；[2,2] 一轮后堆为空并返回 0。若把等重产生的 0 放回堆，答案可能碰巧相同，但堆中会出现题意中不存在的石头，循环状态已不再满足不变量。

代码实现

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

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 first = heap.poll();
            int second = heap.poll();
            if (first != second) {
                heap.offer(first - second);
            }
        }
        return heap.isEmpty() ? 0 : heap.peek();
    }
}

import "container/heap"

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{}
	heap.Init(h)
	for _, s := range stones {
		heap.Push(h, s)
	}

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

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

复杂度分析

时间复杂度：$O(n \log n)$。至多进行 n - 1 轮，每轮包含常数次 $O(\log n)$ 的堆操作；逐个入堆也为 $O(n \log n)$。

空间复杂度：$O(n)$，堆最多保存 n 块石头。

关键点总结

「动态集合中反复取极值并插入新值」是堆的典型使用场景。

本题没有选择策略，数据结构只负责高效、精确地模拟固定规则。

大顶堆连续弹出两次，顺序天然满足 first >= second，差值无需取绝对值。

相等时两块都消失，不要把重量 0 当成新石头放回。

易错点总结

Java 忘记逆序比较器：默认小顶堆会取最轻的两块，违反题意。

循环条件写成堆非空：[1] 会尝试弹出第二块并发生空值或越界错误。

第二块只 peek 不弹出：[8,7] 会把仍在堆中的 7 重复使用，结果错误。

把 second - first 放回：[8,7] 会产生非法的负重量；大顶堆保证应计算 first - second。

一次排序后把差值直接追加到末尾：样例第一轮产生 1 后，末尾已不再代表最大值，下一轮会取错石头。

Go 必须通过 heap.Push、heap.Pop 操作，并让 Push、Pop 使用指针接收者；直接调用类型方法不会维护堆序。

相似题目

题目	难度	考察点
1049. 最后一块石头的重量 II	中等	碰撞对象可以任选，问题等价于把石头分成两堆使差最小，是 01 背包而非模拟
215. 数组中的第K个最大元素	中等	静态集合上求第 k 大，堆只是其中一种解法，还要能对比快速选择
703. 数据流中的第 K 大元素	简单	集合持续新增，用固定容量 `k` 的小顶堆维护，与本题的大顶堆方向相反
347. 前 K 个高频元素	中等	堆里存的是「元素 + 频次」二元组，比较器要按频次而非值
23. 合并 K 个升序链表	困难	堆里存节点，每弹出一个就补入它的后继，是「弹出后补新候选」的典型
373. 查找和最小的 K 对数字	中等	候选空间是二维的，弹出一个下标对后要按规则补入相邻对，还需去重
502. IPO	困难	排序与堆配合：按门槛排序解锁候选、用大顶堆挑收益最高者，操作次数固定为 `k`