LeetCode 1046简单堆 / 优先队列
最后一块石头的重量 图解题解
这道题到底在问什么
每次拿最重的两块石头相撞，重的留下差值，直到剩 0 或 1 块。
- 示例
- [2,7,4,1,8,1] → 1
最优解：一步一步想明白
- 3每轮排序能做，但重复排序浪费。
- 4用最大堆维护当前最重石头，每轮弹两次，再把差值压回。
- 5把所有石头放进最大堆，堆顶永远是当前最重的那块。每轮取最重的两块对撞。
- 6取最重两块 8、7：不等 → 碎石 8−7=1 压回堆。堆顶现在是 4。
- 7取 4、2：剩 4−2=2 压回。
- 8取 2、1：剩 1 压回。
- 9关键帧：取 1、1 —— 相等！两块同时粉碎，什么都不压回堆。堆只剩 [1]。这是本题唯一的分支判断：等就都没、不等才留差。
- 10堆里少于 2 块，停。剩这一块 → 答案 1。（若石头全部两两抵消、堆空，则返回 0）
- 13一句话记住：用最大堆维护当前最重石头，每轮弹两次，再把差值压回。
- 22这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=heap 连刷同类题；卡住时用 AI 答疑问“我的状态定义哪里不稳”。
⚠️ 容易写错的地方
✗ 错：用排序、每轮重新排
✓ 对：用最大堆，取最大 O(log n)
每轮全排序是 O(n log n)、总 O(n²log n)；堆每次只 O(log n)。
✗ 错：相等时把 0 压回堆
✓ 对：相等就都销毁，不压回
压回 0 会污染堆、还凭空多一块；题意是两块都碎。
✗ 错：忘了最后可能空堆
✓ 对：堆空返回 0
全部两两抵消时一块不剩，要返回 0。
完整代码（Python / C++ / Java）
Python
class Solution:
def lastStoneWeight(self, stones):
import heapq
heap = [-x for x in stones] # 取负 → 用最小堆模拟最大堆
heapq.heapify(heap)
while len(heap) > 1:
a = -heapq.heappop(heap) # 最重
b = -heapq.heappop(heap) # 次重
if a != b:
heapq.heappush(heap, -(a - b))
return -heap[0] if heap else 0C++
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> pq(stones.begin(), stones.end()); // 最大堆
while (pq.size() > 1) {
int a = pq.top(); pq.pop();
int b = pq.top(); pq.pop();
if (a != b) pq.push(a - b);
}
return pq.empty() ? 0 : pq.top();
}
};Java
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 a = pq.poll();
int b = pq.poll();
if (a != b) pq.offer(a - b);
}
return pq.isEmpty() ? 0 : pq.peek();
}
}套路模板 · 最大堆模拟
# 最后石头骨架 · 最大堆
heap = 最大堆(stones)
while len(heap) > 1:
a = pop_max(heap) # 最重
b = pop_max(heap) # 次重
if a != b: push(heap, a - b) # 不等才留差
return heap[0] if heap else 0复杂度
时间复杂度
O(n log n)
最多 n 轮，每轮弹两次压一次各 O(log n)
空间复杂度
O(n)
堆存所有石头
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最后一块石头的重量 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
核心思路是什么？+
用最大堆维护当前最重石头，每轮弹两次(最重、次重)，不等就把差值压回，直到剩 ≤1 块。
这道题为什么用「优先队列」，换最直接的暴力解会差在哪？+
优先队列抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。