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

约 4 分钟
文章信息 6 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 字节
标签
数组 堆（优先队列）

题目描述

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

image-20260929073555630

题意分析

每次必须取当前剩余石头中最重的两块相撞。两块等重时都消失，不等重时只留下重量为两者差值的一块，继续重复，直到不足两块。

返回最后一块的重量；若所有石头都消失，返回 0。碰撞对象由当前重量决定，不是让我们任选碰撞策略来优化最后结果，新产生的石头也要参与后续选择。

解法：大顶堆模拟

核心思路

[!blue]

每轮都需要删除两个最大值，并可能插入一个新值，适合用大顶堆维护当前所有石头。堆顶始终是剩余最大值，连续弹出两次，就能得到本轮必须碰撞的 first 和 second，且 first >= second。

若两者相等，不放回任何元素；否则将正差 first - second 插回堆。新石头相对于其他石头的位置可能改变，堆会在插入时重新维护顺序，下一轮仍然能取到真实的最大两块。

初始化时堆与原石头集合相同，每轮弹出与放回也完全遵循题目规则，所以堆中始终准确表示当前存活石头。每次至少减少一块，总会结束；最后堆空就是 0，只剩一项时它就是答案。

Java 的优先队列默认取最小值，需要逆序比较器。Go 通过 Less 中的大于号构造大顶堆，并经由 container/heap 操作；类型自己的 Pop 只负责删除末项，因为容器库在调用它之前已经把要弹出的堆顶移到了末尾。

解题步骤

  1. 建立大顶堆，将全部石头加入。
  2. 堆中至少有两项时，连续弹出两次，得到本轮最大与次大重量。
  3. 等重就都消失；不等重则把差值重新入堆。
  4. 重复直到堆中不足两项，空堆返回 0，否则返回唯一石头的重量。

代码实现

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) {
            // 连续弹出两次，保证 first 不小于 second。
            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 不小于 second。
        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+1))$，最多 n-1 轮，每轮进行常数次堆操作。
  • 空间复杂度：$O(n)$，堆保存剩余石头。

关键点总结

[!green]

  • 题目已经固定每轮选择规则，算法只需准确维护变化后的最大两项。
  • 堆在删除和插入后恢复顺序，差值石头也能自然参与下一轮。
  • 每轮石头数减少，终止时堆中的集合与真实剩余状态完全一致。

易错点总结

[!yellow]

  • 使用默认小顶堆，会拿出最轻的两块，模拟成另一套规则。
  • 循环只检查堆非空，剩一块时第二次弹出会失败。
  • 只读取第二块而不从堆中移除，会让已经碰撞的石头再次出现。
  • 差值只保存在临时变量而不放回堆，后续碰撞就遗漏了新石头。
  • 直接调用 Go 类型上的 Push 或 Pop，只会改切片而不维护堆序，应使用容器库入口。
  • 等重时放回零会增加无意义的后续处理，直接让两块消失即可。

相似题目

题目 难度 关联与区别
1167. 连接木棍的最低费用 中等 同样反复取极值合并，但原题取最小两块并累加费用，本题取最大两块相减。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/45215791
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！