这次我们来看一道经典的力扣LeetCode题目1046. 最后一块石头的重量。这道题本身不难但它是理解“大顶堆”这一数据结构及其在C STL中应用的绝佳案例。很多人在学习数据结构时感觉理论和代码是割裂的这道题恰好提供了一个“知行合一”的契机——用具体的算法问题去深刻体会数据结构的威力。本文将带你从零开始一步步拆解这道题。核心不是背答案而是理解为什么用大顶堆、如何在C STL中实现、以及如何将这种解题思路迁移到其他问题上。我们会重点关注代码实现、STL的priority_queue用法、以及如何通过这道题巩固堆数据结构的知识。无论你是正在刷题准备面试还是想深化对数据结构的理解这篇文章都值得一看。1. 核心能力速览在深入代码之前我们先快速把握这道题的核心要点和所需的“技术栈”。能力项说明问题类型算法模拟题贪心思想核心数据结构大顶堆 (Max-Heap)最佳时间复杂度O(n log n)空间复杂度O(n)关键C STL工具std::priority_queue解题思路每次选取最重的两块石头碰撞模拟过程直至剩余0或1块石头前置知识数组、基本循环、堆的概念适合读者算法初学者、希望理解堆的应用、准备力扣/面试2. 适用场景与使用边界这道题虽然场景设定是“石头碰撞”但其核心是动态获取最大值并更新集合的模型。理解这个模型你就能解决一系列类似问题。它非常适合以下场景算法学习与面试准备是考察对堆优先队列理解的经典入门题。理解贪心策略每一步都采取当前最优选择取最重的两块石头。掌握STLpriority_queue学习如何用现成容器快速实现算法避免手写堆。问题建模训练将“碰撞销毁”抽象为“从集合中取出两个最大元素并进行运算后可能放回”的通用操作。它的局限性问题本身较为简单不适合用来考察复杂的动态规划或图算法。作为教学案例它更侧重于数据结构的应用而非算法的最优化其解法已接近最优。重要提醒在解决任何算法问题时都应注重思路的清晰和代码的健壮性而非单纯记忆。本文提供的代码和思路请在你的本地开发环境如VS Code、CLion中亲自运行和调试以达到最佳学习效果。3. 环境准备与前置条件为了能顺畅地跟随本文进行代码实践你需要准备好基础的C开发环境。这并不复杂。编译器支持C11或更高版本的编译器。推荐GCC(MinGW-w64) 适用于Windows可通过MSYS2或MinGW安装。Clang 在macOS和Linux上常见。Microsoft Visual C 如果你使用Visual Studio。代码编辑器或IDEVisual Studio Code (VS Code) 轻量级通过安装C/C扩展获得强大支持。这也是当前非常流行的选择。CLion JetBrains出品功能强大的跨平台C/C IDE。Visual Studio Windows平台下的重量级IDE功能全面。基础C知识你需要了解基本数据类型、数组vector。循环while,for。条件判断if。标准模板库STL中vector和priority_queue的基本使用。力扣或本地调试你可以直接在力扣的在线编辑器上做题但为了更深入理解建议在本地创建项目编写、编译并运行代码。4. 问题分析与算法思路题目“最后一块石头的重量”描述如下 有一堆石头每块石头的重量都是正整数。 每一回合从中选出最重的两块石头然后将它们一起粉碎。假设石头的重量分别为x和y且x y。如果x y那么两块石头都会被完全粉碎如果x ! y那么重量为x的石头将会完全粉碎而重量为y的石头新重量为y - x。 游戏结束后最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下就返回0。思路拆解核心操作每一回合都需要找到当前所有石头中最重的两块。数据结构选择如果每次都用数组然后排序找最大值一次操作是O(n log n)模拟n轮总复杂度会很高。更优的选择是大顶堆。堆可以在O(log n)的时间内取出最大值并在O(log n)的时间内插入新元素完美契合“不断取出最大值并可能插入新值”的操作序列。算法流程 a. 将所有石头的重量放入一个大顶堆。 b. 当堆中元素数量大于1时循环 - 取出堆顶当前最重石头y。 - 再次取出堆顶当前次重石头x。 - 如果y x则将y - x的重量重新放入堆中。 如果相等则两者都销毁无需放回任何东西 c. 循环结束后如果堆为空返回0否则返回堆中仅剩的那个石头的重量。这个思路清晰地将问题转化为了对堆数据结构的操作。5. C STL 中的大顶堆实现在C中我们不需要手写一个堆。标准模板库STL提供了std::priority_queue容器适配器它默认就是一个大顶堆。5.1priority_queue基本用法#include queue #include vector #include iostream int main() { // 定义一个存储int的大顶堆 std::priority_queueint max_heap; // 插入元素 max_heap.push(3); max_heap.push(1); max_heap.push(4); max_heap.push(1); max_heap.push(5); // 访问堆顶元素最大元素 std::cout Top element: max_heap.top() std::endl; // 输出 5 // 弹出堆顶元素 max_heap.pop(); // 移除 5 std::cout Top element after pop: max_heap.top() std::endl; // 输出 4 // 检查是否为空 while (!max_heap.empty()) { std::cout max_heap.top() ; max_heap.pop(); } // 输出: 4 3 1 1 return 0; }关键点push(val): 插入元素时间复杂度O(log n)。top(): 返回堆顶元素最大值时间复杂度O(1)。pop(): 删除堆顶元素时间复杂度O(log n)。empty(): 判断堆是否为空。5.2 为什么不用vector然后每次排序我们来对比一下vector 排序每次操作需要O(n log n)排序模拟整个过程可能需要O(n^2 log n)的时间在石头数量多时效率极低。priority_queue每次取最大和插入都是O(log n)模拟整个过程是O(n log n)效率高出一个数量级。这就是选择合适数据结构的意义——将算法复杂度从不可接受变为高效可行。6. 完整代码实现与逐行解析掌握了priority_queue实现题目就水到渠成了。下面给出两种风格的代码一种是力扣答题框内的简洁风格另一种是本地测试更清晰的风格。6.1 力扣风格简洁版#include queue #include vector using namespace std; class Solution { public: int lastStoneWeight(vectorint stones) { // 1. 创建一个大顶堆 priority_queueint max_heap; // 2. 将所有石头重量放入堆中 for (int weight : stones) { max_heap.push(weight); } // 3. 模拟碰撞过程 while (max_heap.size() 1) { // 取出最重的两块石头 int y max_heap.top(); max_heap.pop(); // 最重 int x max_heap.top(); max_heap.pop(); // 次重 // 如果重量不同将剩余部分放回堆中 if (y x) { max_heap.push(y - x); } // 如果重量相同两者都销毁无需操作 } // 4. 返回结果 return max_heap.empty() ? 0 : max_heap.top(); } };6.2 本地测试风格带详细注释和测试#include iostream #include queue #include vector using namespace std; int lastStoneWeight(vectorint stones) { // 使用优先级队列模拟大顶堆 // 注意priority_queueType, Container, Compare // 默认是 lessint即大顶堆 priority_queueint max_heap; // 将初始石头放入堆中 cout 初始石头重量: ; for (int stone : stones) { cout stone ; max_heap.push(stone); } cout endl 构建大顶堆完成。 endl; int round 1; // 当堆中至少有两块石头时继续碰撞 while (max_heap.size() 1) { // 取出当前最重的两块石头 int first max_heap.top(); // 最重 max_heap.pop(); int second max_heap.top(); // 次重 max_heap.pop(); cout \n第 round 轮碰撞: ; cout 石头 first 和石头 second; if (first second) { cout 重量相等完全粉碎。 endl; } else { int newStone first - second; // 因为first second cout 碰撞后剩余石头重量为: newStone endl; max_heap.push(newStone); // 将剩余部分放回堆中 } round; } // 返回最终结果 if (max_heap.empty()) { cout \n所有石头均已粉碎剩余重量为 0。 endl; return 0; } else { int lastStone max_heap.top(); cout \n最后剩余一块石头重量为: lastStone endl; return lastStone; } } int main() { // 测试用例1: 示例 [2,7,4,1,8,1] vectorint stones1 {2, 7, 4, 1, 8, 1}; cout 测试用例 1 endl; int result1 lastStoneWeight(stones1); cout 最终结果: result1 endl; // 应输出 1 cout \n 测试用例 2 endl; // 测试用例2: 所有石头重量相同 [5,5,5,5] vectorint stones2 {5, 5, 5, 5}; int result2 lastStoneWeight(stones2); cout 最终结果: result2 endl; // 应输出 0 cout \n 测试用例 3 endl; // 测试用例3: 单块石头 [100] vectorint stones3 {100}; int result3 lastStoneWeight(stones3); cout 最终结果: result3 endl; // 应输出 100 return 0; }将这段代码复制到你的本地IDE如VS Code中编译运行你可以清晰地看到每一轮碰撞的过程这对于理解算法执行流程非常有帮助。7. 复杂度分析与性能观察理解算法不仅要会写还要知道它为什么好。时间复杂度O(n log n)建堆将n个元素依次插入大顶堆每次插入O(log n)总复杂度O(n log n)。更精确的建堆方式可以是O(n)但使用priority_queue逐项插入就是O(n log n)。模拟过程最坏情况下每次碰撞都产生一个新石头放回堆中可能进行约n次操作取两个可能放回一个。每次取最大和插入都是O(log n)。因此模拟过程也是O(n log n)。综合来看主导因素是O(n log n)。空间复杂度O(n)我们需要一个堆来存储所有石头最坏情况下存储n个元素。性能观察点在实际运行或力扣提交时这个算法对于题目约束1 stones.length 30,1 stones[i] 1000是绰绰有余的。即使石头数量扩大到10^5O(n log n)的算法也能在合理时间内完成。你可以尝试用更大的随机数组测试感受其效率。8. 常见问题与排查方法在实现过程中你可能会遇到一些典型问题。这里列出并给出解决方案。问题现象可能原因排查方式解决方案编译错误‘priority_queue’ was not declared没有包含必要的头文件。检查代码开头是否有#include queue。添加#include queue。对于vector也需要#include vector。运行时错误或逻辑错误结果不对1. 没有处理堆为空的情况。2. 取石头顺序弄反应先取y再取x。3. 碰撞后条件判断有误。使用本地测试代码打印每一轮碰撞的石头重量和剩余堆的状态。仔细检查while循环条件和if (y x)的逻辑。确保y是第一次pop出来的。力扣提交超时使用了低效的方法如每次循环都排序。审查算法复杂度。对于本题O(n^2)的算法在数据量大时会超时。必须使用堆priority_queue来保证O(n log n)的复杂度。如何实现小顶堆默认priority_queue是大顶堆。查阅STL文档。定义时指定比较器priority_queueint, vectorint, greaterint min_heap;想看到堆内部元素顺序priority_queue不提供遍历方法。这是容器适配器的设计无法直接查看。如果需要调试可以临时将元素拷贝到另一个容器中查看。但注意这会破坏堆。9. 举一反三堆数据结构的其他应用场景通过这道题你应该体会到堆的核心功能动态维护一组数据中的最值。一旦掌握这个精髓很多问题都可以迎刃而开。以下是一些力扣上同样使用堆优先队列的经典题目建议按顺序练习剑指 Offer 40. 最小的k个数 / 力扣 347. 前 K 个高频元素使用小顶堆或大顶堆维护频率最高的K个元素。力扣 23. 合并K个升序链表使用小顶堆维护K个链表当前的最小节点。力扣 215. 数组中的第K个最大元素使用小顶堆维护当前最大的K个元素堆顶即为第K大。力扣 253. 会议室 II使用小顶堆维护正在进行的会议的结束时间以判断是否需要新房间。力扣 295. 数据流的中位数使用一个大顶堆和一个小顶堆协同工作动态维护中位数。解题模板化当你遇到一个问题需要频繁进行以下操作时就应该考虑堆“每次都需要当前最大/最小的元素”“动态添加元素并随时可能询问当前极值”“维护一个大小固定为K的集合并总是关注其边界值”10. 最佳实践与学习建议从暴力法思考起不要一上来就找最优解。先想最直观的解法比如本题每次循环排序分析其复杂度瓶颈再思考如何用更高效的数据结构堆来优化。这个过程能极大提升你的算法设计能力。善用STL但理解原理priority_queue让我们免于手写堆但你必须理解堆的插入(push)、删除(pop)、取顶(top)操作的时间复杂度为什么是O(log n)和O(1)。建议至少手动实现一次堆的heapify、push、pop操作。本地调试优于在线提交在力扣上“提交通过”只是一个结果。在本地IDE中运行添加打印语句观察变量变化、数据流转才能让你真正吃透算法。画图辅助理解对于堆这种树形结构在纸上画一画插入、删除的过程比单纯看代码要直观得多。归纳总结做完这道题把它归入你的“堆-优先队列”知识卡片中并记录其核心思想动态求最值和代码模板。回到“知行合一”这道力扣1046题就是一个完美的桥梁。它用“石头碰撞”这个有趣的问题作为“行”引导你去实践“堆”这个数据结构之“知”。当你用几行priority_queue的代码优雅地解决问题时你不仅通过了一道题更内化了一种高效处理极值问题的方法论。这种从具体问题中抽象出模型再选用合适数据结构解决的能力才是算法学习中最宝贵的收获。