LeetCode 1046简单堆 / 优先队列
最后一块石头的重量 图解题解
这道题到底在问什么
每次取两块最重的石头 x≤y 相撞：若 x==y 两块都碎；否则碎掉 x、y 变成 y−x。求最后剩下那块（没有则 0）。
- 输入
- stones=[2,7,4,1,8,1]
- 输出
- 1
最优解：一步一步想明白
- 3思路浓缩成一句：反复取最大、动态加入 → 大顶堆（优先队列）。先把 6 块石头逐个插堆（上浮），再开始对撞。
- 4插入石头 2。
- 5堆里只有它一个，自然就是堆顶。
- 6插入石头 7。
- 7子节点 7 比父节点 2 大，违反大顶堆，交换二者让大的往上走。
- 87 浮到了堆顶，成为当前最重的石头。
- 9插入石头 4。
- 10比较 4 和它的父节点 7：父更大（或相等），大顶堆性质已满足，停止上浮。
- 11插入石头 1。
- 12比较 1 和它的父节点 2：父更大（或相等），大顶堆性质已满足，停止上浮。
- 13插入石头 8。
- 14子节点 8 比父节点 2 大，违反大顶堆，交换二者让大的往上走。
- 15子节点 8 比父节点 7 大，违反大顶堆，交换二者让大的往上走。
- 168 浮到了堆顶，成为当前最重的石头。
- 17插入石头 1。
- 18比较 1 和它的父节点 4：父更大（或相等），大顶堆性质已满足，停止上浮。
- 19六块石头都进堆了，堆顶是最重的 8。大顶堆建好，开始对撞。
- 20取出堆顶 8——它就是当前最重的石头。
- 21把末尾的石头 1 临时补到堆顶占位，接下来让它下沉到合适位置。
- 22堆顶 1 比孩子 7 小，交换：把更大的孩子换上来，最大值重新坐回堆顶。
- 23堆顶 1 比孩子 2 小，交换：把更大的孩子换上来，最大值重新坐回堆顶。
- 24堆顶 7 已不小于它的孩子，大顶堆恢复，下沉结束。
- 25取出堆顶 7——它就是当前最重的石头。
- 26把末尾的石头 1 临时补到堆顶占位，接下来让它下沉到合适位置。
- 27堆顶 1 比孩子 4 小，交换：把更大的孩子换上来，最大值重新坐回堆顶。
- 28堆顶 4 已不小于它的孩子，大顶堆恢复，下沉结束。
- 29两块最重的石头 8 和 7 相撞：8 − 7 = 1，碎出一块 1 的新石头，放回堆里。
- 30把对撞产生的石头 1 放回堆末尾，再上浮归位。
- 31比较 1 和它的父节点 2：父更大（或相等），大顶堆性质已满足，停止上浮。
- 32取出堆顶 4——它就是当前最重的石头。
- 33把末尾的石头 1 临时补到堆顶占位，接下来让它下沉到合适位置。
- 34堆顶 1 比孩子 2 小，交换：把更大的孩子换上来，最大值重新坐回堆顶。
- 35堆顶 2 已不小于它的孩子，大顶堆恢复，下沉结束。
- 36取出堆顶 2——它就是当前最重的石头。
- 37把末尾的石头 1 临时补到堆顶占位，接下来让它下沉到合适位置。
- 38堆顶 1 已不小于它的孩子，大顶堆恢复，下沉结束。
- 39两块最重的石头 4 和 2 相撞：4 − 2 = 2，碎出一块 2 的新石头，放回堆里。
- 40把对撞产生的石头 2 放回堆末尾，再上浮归位。
- 41子节点 2 比父节点 1 大，违反大顶堆，交换二者让大的往上走。
- 42子节点 2 比父节点 1 大，违反大顶堆，交换二者让大的往上走。
- 432 浮到了堆顶，成为当前最重的石头。
- 44取出堆顶 2——它就是当前最重的石头。
- 45把末尾的石头 1 临时补到堆顶占位，接下来让它下沉到合适位置。
- 46堆顶 1 已不小于它的孩子，大顶堆恢复，下沉结束。
- 47取出堆顶 1——它就是当前最重的石头。
- 48把末尾的石头 1 临时补到堆顶占位，接下来让它下沉到合适位置。
- 49堆顶 1 已不小于它的孩子，大顶堆恢复，下沉结束。
- 50两块最重的石头 2 和 1 相撞：2 − 1 = 1，碎出一块 1 的新石头，放回堆里。
- 51把对撞产生的石头 1 放回堆末尾，再上浮归位。
- 52比较 1 和它的父节点 1：父更大（或相等），大顶堆性质已满足，停止上浮。
- 53取出堆顶 1——它就是当前最重的石头。
- 54把末尾的石头 1 临时补到堆顶占位，接下来让它下沉到合适位置。
- 55堆顶 1 已不小于它的孩子，大顶堆恢复，下沉结束。
- 56取出堆顶 1——它就是当前最重的石头。
- 57把末尾的石头 1 临时补到堆顶占位，接下来让它下沉到合适位置。
- 58堆顶 1 已不小于它的孩子，大顶堆恢复，下沉结束。
- 59两块石头一样重（1 和 1）相撞：两块都碎光，什么都不放回。
- 60堆里只剩一块石头 1，再也凑不出两块来撞，它就是最后的答案。
⚠️ 容易写错的地方
✗ 错：每轮只 pop 一块就判断
✓ 对：一轮要 pop 两块（最重 + 次重）
相撞是两块石头的事
✗ 错：diff==0 还往堆里 push 0
✓ 对：只有 diff>0 才放回
放个 0 进去会污染堆、还可能多撞一轮
✗ 错：Python 直接用 heapq 当大顶堆
✓ 对：heapq 是小顶堆，必须取负
不取负会每次拿到最轻的两块，答案全错
完整代码（Python / C++ / Java）
Python
import heapq
def lastStoneWeight(stones):
h = [-s for s in stones] # 取负模拟大顶堆
heapq.heapify(h)
while len(h) > 1:
y = -heapq.heappop(h) # 最重
x = -heapq.heappop(h) # 次重
if y > x:
heapq.heappush(h, -(y - x))
return -h[0] if h else 0C++
int lastStoneWeight(vector<int>& stones){
priority_queue<int> pq(stones.begin(), stones.end());
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();
}Java
import java.util.PriorityQueue;
import java.util.Collections;
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> pq =
new PriorityQueue<>(Collections.reverseOrder());
for (int s : stones) pq.offer(s);
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();
}
}复杂度
时间
O(n log n)
最多 n 轮，每轮两次 pop + 一次 push，各 O(log n)
空间
O(n)
堆里最多放 n 块石头
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最后一块石头的重量 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
Java 里怎么得到大顶堆？+
PriorityQueue 默认是小顶堆（自然序）。传入 Collections.reverseOrder() 比较器即得大顶堆；也可写 (a,b)->b-a，但元素大时注意 b-a 溢出，稳妥用 Integer.compare(b,a)。
这题能不能不用堆？+
能。石头重量范围小（≤1000）时可用计数/桶，或排序后用 multiset/有序结构模拟；但堆是最直观、通用且复杂度优秀的写法，面试首选。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 最后一块石头的重量 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。