力扣1046这道“最后一块石头的重量”，我常把它当作面试里考察大小堆和优先队列的入门练兵场。题目本身很直白：你有一堆石头，每次从里面拎出最重的两块，按规则粉碎一轮，剩下的差再丢回去，直到剩一块或全部消失。看起来只是在做“模拟”，但选对数据结构之后，代码可以短到十行以内。这篇文章我会从命题角度拆题，再把C++优先队列的用法、大堆小堆怎么选、完整实现和踩坑点一次讲透，最后再带出几道同类型的衍生题，方便你把这个套路彻底吃透。
1. 题目拆解：为什么“反复取最大”会指向优先级队列
1.1 原题描述与最直白的粗暴做法
先把题目复述一遍：数组stones里的每个元素代表一块石头的重量，每一轮你都要选择最重的两块石头，设重量为x和y，并且假设x <= y。然后按规则处理：
- 如果
x == y，两块石头一起被完全粉碎，消失； - 如果
x != y，那么重量为x的石头会被粉碎消失，重量为y的石头会变成y - x，并作为新石头放回石头堆里。
整个过程一直重复，直到最多只剩下一块石头为止。如果最终剩下一块，就返回它的重量；如果一块都不剩，返回0。
用示例来演算一下：[2,7,4,1,8,1]，第一轮挑出7和8，因为7小于8，所以7消失，8变成1，此时石头重量为[2,4,1,1,1]；第二轮挑出2和4，2消失，4变成2，石头变成[2,1,1,1]；第三轮挑出2和1，1消失，2变成1，石头变成[1,1,1]；第四轮挑出1和1，两者都消失，只剩一个1，最终返回1。
很多人第一反应是“那我每次排个序，从末尾取两个数不就完了？”这个思路确实是最直白的模拟：把数组按从小到大排序，每次取最后两个元素，按照规则把差值再插回去，然后再排序。问题是这个做法每一步都要维持数组有序，每次插入最坏情况需要移动O(n)个元素，整体复杂度会到O(n^2 log n)级别，代码写起来也啰嗦。
1.2 模拟流程背后藏着的两个关键约束
这道题看起来是模拟，但如果你往深想一层，会发现整个流程有两个核心约束直接决定了数据结构选型：
第一，每一轮都必须拿到当前所有石头里最大的值。注意，这里的“最大值”不是一次性的，而是每轮都在动态变化。因为每次粉碎之后，可能会产生一个全新的差值，这个差值不是一个固定的小数，它可能又成为下一轮的最大值。也就是说，这个“最大值集合”是不断被修改的，今天最大的石头，下一轮可能被磨成了小石子，也可能被打碎消失。
第二，整个过程只需要关心极值，不需要关心中间顺序。比如当前堆里有5、3、2，下一轮只需要知道5和3是谁，至于2排在第几，完全无所谓。这就意味着，维持一个完全有序的结构是浪费的。我们需要的是一个“能快速拿到最大值，同时支持修改后继续快速拿到最大值”的容器。
基于这两个约束，优先级队列几乎是本能选项。它抽象出来的语义就是“最高优先级先出队”，每次拿走最大元素的时间只需要O(log n)，插入一个元素也只需要O(log n)。相比之下，排序方案在每一步都要维护全序关系，白花了大量计算在全量有序上，而这恰恰是题目根本不需要的。
2. 大小堆怎么选：C++优先队列的默认行为与构造细节
2.1 默认大堆：恰好满足“每次取最重石头”
在C++标准库里，priority_queue是一个容器适配器，底层默认使用vector，并且默认构造出来的是大堆，也就是优先级队列的top()会返回当前所有元素中“最大”的那个。
为什么默认是大堆？因为priority_queue的模板参数里，比较器默认是std::less，而std::less在堆算法里会把最大的元素放在堆顶。如果你看过<queue>头文件的实现，就会看到类似这样的声明：
template<class T, class Container = vector<T>, class Compare = less<T>> class priority_queue;所以当你写下：
priority_queue<int> pq;时，pq.top()就是所有已入队元素的最大值。对于“最后一块石头的重量”这道题，我们要的恰恰就是“最重”的石头，所以直接用默认的大堆就行。这也是大部分C++解法看起来特别简短的原因，因为标准库把这个能力直接送给了我们，不需要自定义任何比较器。
有同学可能会问：大堆和小堆里“堆”到底是什么？简单说，堆是一棵完全二叉树，但它在内存里是用数组顺序存储的。大堆要求每个父节点都大于等于它的子节点，因此根节点就是最大值。由于我们只需要盯着根节点，而不关心其他节点的排序，所以建堆、取堆顶、插入新元素的代价都很低，这就是它比全量排序高效的核心原因。
2.2 如果需要小堆：priority_queue的完整声明方式
虽然这道题默认大堆就够用，但面试里经常会把场景反过来，要求“每次取最小”，这个时候就必须要会构造一个小堆。C++里最典型的写法是：
#include <queue> #include <vector> #include <functional> priority_queue<int, vector<int>, greater<int>> pq;注意三点：
- 第二个参数
vector<int>是底层容器，默认是它，理论上可以换，但一般不会换，因为vector和堆算法的适配性最好； - 第三个参数
greater<int>是函数对象，它让比较逻辑变成“父节点小于子节点”，于是堆顶就是最小值； - 需要包含
<functional>头文件，否则greater根本不在编译器的视野里，会出现“greater is not a member”这类报错。
另外，如果你对自定义类型使用优先队列，比方说按某个字段排序，那就不能直接用greater了，要写一个仿函数或者lambda表达式，并且在构造priority_queue时把比较器传进去。这里给一个lambda版本作为参考：
auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) { return a.second > b.second; // 小堆：second较小的优先级高 }; priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);decltype(cmp)拿到lambda类型，构造时把cmp传进去。这种写法在一些“按频率排序”的TopK题目里很常见，值得顺手记下来。
3. 从暴力到堆模拟：完整C++实现与复杂度复盘
3.1 能过但没灵魂的暴力方案
先给一个暴力版本的实现，方便对比。由于题目限制stones.length <= 30，就算你用最笨的方式也能通过力扣的评测，所以我称之为“能过但没灵魂”。
思路是每轮都用sort从大到小排序，然后取前两个数处理。代码如下：
class Solution { public: int lastStoneWeight(vector<int>& stones) { while (stones.size() > 1) { sort(stones.begin(), stones.end(), greater<int>()); int y = stones[0]; int x = stones[1]; stones.erase(stones.begin(), stones.begin() + 2); if (x != y) { stones.push_back(y - x); } } return stones.empty() ? 0 : stones[0]; } };这段代码每次排序后取最大的两个，然后erase掉开头两个元素，再把差值放回去。排序本身是O(n log n)，加上erase在vector头部删除元素的代价是O(n)，一共要循环n轮左右，最坏复杂度接近O(n^2 log n)。由于n<=30，实测完全跑得动。但要是面试官把石头数量改成10^5，这个代码立刻超时。所以暴力方案的意义只在于帮助验证题目理解，不适合作为最终答案。
3.2 用priority_queue写出的最终解法
接下来是我最推荐的标准写法，也是力扣官方题解同思路的C++实现：
class Solution { public: int lastStoneWeight(vector<int>& stones) { priority_queue<int> pq; for (int weight : stones) { pq.push(weight); } while (pq.size() > 1) { int first = pq.top(); pq.pop(); int second = pq.top(); pq.pop(); if (first > second) { pq.push(first - second); } // 如果 first == second，则两块都消失，不需要 push } return pq.empty() ? 0 : pq.top(); } };逐段解释一下这十几行代码的意图：
- 先把所有石头重量压进优先队列，建立一个大堆，堆顶始终是当前最重的石头；
- 循环条件
pq.size() > 1，确保堆里至少有2块石头才进行粉碎操作，避免访问空堆或只取到一块石头； - 连续两次
top()和pop()，拿到最重和次重的两块石头。因为是大堆，所以first >= second一定成立； - 如果两块重量不同，把差值重新塞回堆；如果相同，什么也不做，因为两个都消失了；
- 循环结束后，要么堆空，要么只剩一块石头。堆空返回0，否则返回堆顶。
这个代码最优雅的地方在于，它不需要维护任何多余状态。每次粉碎后的新重量，只需一次压堆操作就自动回到了正确的位置，下一轮top()依然能拿到最大值。整段代码没有任何手写的排序、交换、移动逻辑，堆内部自己完成了所有维护工作。
3.3 复杂度分析与扩展数据范围表现
复杂度算起来非常清晰：
- 建堆阶段：把
n个元素依次push，单次是O(log n)，总时间是O(n log n)； - 模拟阶段：最多进行
n - 1轮粉碎，因为每轮至少消灭一块石头（相等时消灭两块）。每轮两次pop、最多一次push，每次操作都是O(log n)，最坏也是O(n log n)； - 空间复杂度：
priority_queue底层vector存储元素，额外空间O(n)。
如果把stones.length上限放大到10^5，O(n log n)的复杂度依然可以舒适通过。这也是这道题作为“堆”教学题的典型特征：数据范围不大，但数据结构的价值依然能体现出来。从暴力到堆模拟的优化，本质是把“反复找最大”的代价从O(n)降到了O(log n)，而堆的数学性质保证了每次都只花O(log n)，不随当前数据规模发生波动。
4. 避坑实录：priority_queue使用中那些编译器不会教你的细节
4.1 greater类型与functional头文件的坑
我第一次用priority_queue<int, vector<int>, greater<int>>时，只写了#include <queue>，结果编译直接报错。原因是greater这个函数对象模板定义在<functional>头文件里，<queue>内部不一定帮你完整引入它。你必须在源文件顶部额外加上：
#include <functional>这个坑在力扣的在线编辑器里尤其容易被忽略，因为有些编译器版本的头文件互相包含比较“慷慨”，本地能编译过去，换到评测机上就崩，非常影响调试心情。
另一个常见误解是把greater<int>写成greater<int>()。在模板参数位置，你传递的是类型，不是对象，所以写作greater<int>；在构造priority_queue对象时，如果要传比较器实例，才需要带上括号：
priority_queue<int, vector<int>, greater<int>> pq; // 模板参数，无括号 priority_queue<int, vector<int>, greater<int>> pq(greater<int>()); // 显式传对象，有括号平时直接写第一种就够了，但两种写法都要能看懂，面试手写代码时偶尔会考你是否理解这两者的区别。
4.2 判空与边界条件：什么时候该检查size()
这道题的边界条件隐藏在循环退出里。很多人会下意识把循环写成：
while (!pq.empty()) { int first = pq.top(); pq.pop(); int second = pq.top(); pq.pop(); // ... }这个写法是错的。当堆里只剩一块石头时，second = pq.top()这一行就会访问一个空堆，行为是未定义的，轻则返回脏数据，重则直接崩溃。正确做法是循环前先判断pq.size() > 1，或者先检查pq.empty()再决定是否继续。我的个人习惯是：
while (pq.size() > 1) { // 安全弹出两个元素 }因为这道题最多只会剩一块石头或空堆，size() > 1是最贴近业务条件的判断。如果你写while (!pq.empty())，还得在内部再判一次：
if (pq.empty()) break;那样既啰嗦又容易出漏判。
另外，在返回结果时，很多人会直接return pq.top();。但如果整个过程所有石头都恰好两两抵消，堆会是空的，此时访问pq.top()就会越界。正确写法是：
return pq.empty() ? 0 : pq.top();4.3 反复提交才发现：题目输入范围虽小，代码习惯不能省
力扣这道题给出的stones.length最多只有30，stones[i]最大也只有1000，所以就算你用暴力排序版也能过，但这并不代表边界处理可以敷衍。我在实际练习中发现，越简单的题越容易考出“仔细程度”：有些提交因为忽略空堆返回0导致WA，有些因为写了int类型没问题，但把题目变体改成百万级数字时才会暴露溢出风险。
如果面试官临时把题改一下，让石头重量最大到2^31，那么first - second的结果依然不可能超过原最大值（毕竟差的绝对值一定小于较大的那个数，而较大的那个数是从原有元素来的），所以int其实还能撑住。但如果你要用累计和、乘法之类，就一定要考虑类型。稳妥的做法是直接把元素用long long存储：
priority_queue<long long> pq; for (int w : stones) pq.push(static_cast<long long>(w));虽然这道题没必要，但能体现你思考过数据溢出边界，这是面试官很看重的工程习惯。
5. 从这道每日一题延伸出去：大小堆题型套路与扩展练习
5.1 同套路题目：TopK、数据流中位数、合并K个链表
“每次操作拿最大/最小，处理后放回”这个模型，在力扣里还有大量变种。我系统性列一下可以用大小堆直接解决的经典题，方便你按图索骥：
| 题目类型 | 核心需求 | 用大堆还是小堆 | 大致思路 |
|---|---|---|---|
| 数组中的第K个最大元素 | 找到第K个最大值 | 小堆，维护大小为K | 堆容量超过K就弹出堆顶，最后堆顶就是答案 |
| 数据流中的第K大元素 | 动态插入，查第K大 | 小堆，维护大小为K | 每次插入后淘汰最小，堆顶始终是第K大 |
| 前K个高频元素 | 按频率取前K个 | 小堆，按频率比较 | 先统计频率，再维护大小为K的最小堆 |
| 数据流的中位数 | 动态求中位数 | 大堆+小堆 | 左侧大堆存较小一半，右侧小堆存较大一半，平衡两边数量 |
| 合并K个升序链表 | 每次取当前最小节点 | 小堆 | 把所有链表头入堆，每轮弹出最小节点，再把它的next入堆 |
| 最后一块石头的重量 | 每次取最大并放回差 | 大堆 | 本题核心 |
从这张表能看出，TopK类问题的通用套路就是“固定容量的堆”：如果要大的前K个，就用小堆；如果要小的前K个，就用大堆。因为堆容量固定为K，每次插入和弹出的总代价是O(log K)，整体复杂度是O(n log K)，非常优秀。
5.2 手写堆版本：如果你遇到禁用优先队列的面试题
有些面试官会故意说“不用标准库的priority_queue，你现场写一个堆”。这时候你需要了解底层原理。其实手写一个最简大堆并不复杂，核心是vector存元素加两个函数：push_heap和pop_heap。
class MaxHeap { vector<int> data; public: void push(int val) { data.push_back(val); int i = data.size() - 1; while (i > 0 && data[(i - 1) / 2] < data[i]) { swap(data[(i - 1) / 2], data[i]); i = (i - 1) / 2; } } int top() const { return data[0]; } void pop() { data[0] = data.back(); data.pop_back(); int i = 0; int n = data.size(); while (true) { int largest = i; int left = i * 2 + 1; int right = i * 2 + 2; if (left < n && data[left] > data[largest]) largest = left; if (right < n && data[right] > data[largest]) largest = right; if (largest == i) break; swap(data[i], data[largest]); i = largest; } } bool empty() const { return data.empty(); } int size() const { return data.size(); } };这段代码的关键在于两个调整过程：push时从新元素位置向上比较，直到满足父节点大于子节点；pop时把最后一个元素移到堆顶，然后向下调整。理解了这两个过程，你就明白了为什么priority_queue内部可以在O(log n)完成操作——因为它只是在操作一颗完全二叉树的数组表示，而不是什么神秘魔法。
5.3 “贪心 + 堆”模型能解决哪一类真实问题
最后把格局打开一点。“每次挑最大/最小，处理后放回”这个模型，并不只存在于算法题里，它在真实系统里也很常见。比如任务调度：系统里有一批任务，每个任务有优先级和预计执行时间，每次从就绪队列里取出优先级最高的任务执行，中途被抢占的任务又会重新进入队列，这和“取两块最大石头，粉碎后再放回”本质是一样的。又比如网络报文转发中的拥塞控制，同样需要动态从一堆候选连接里挑最小RTT或最大带宽的连接。
所以，千万不要把这道每日一题仅仅当成一道“模拟题”。它真正让你练的是建立一种直觉：当一个过程反复需要动态极值时，堆就是那把最顺手的工具。你不需要对全部数据排序，只需要时刻掌握最值，并且在最值被消费之后，快速找到下一个最值。这个能力在面试中经常换着花样出现，今天考石头，明天考链表，后天考数据流，底层都是同一套思路。
我在刷题时还有一个习惯：每做完一道堆相关题目，就顺手把它归类到“大小堆”专题下，然后用同一模板尝试改写。比如把“最后一块石头的重量”改成“每次取两块最小的石头，大的消失，小的变成它们的和”，稍微改造一下就能变成另一道题。这样练上十道八道，你就能完全摆脱对题目的死记硬背，看到“反复取最值”这几个字，自然会想到priority_queue。如果你还没试过这个专题化刷法，建议从今天这道题开始。
