C++ 最大堆模拟：最后一块石头的重量

一、题目描述

题目链接：最后一块石头的重量

题目描述： 有一堆石头，每块石头的重量都是正整数。每一回合，从中选出两块最重的石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头完全粉碎，而重量为 y 的石头新重量为 y - x。 最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

示例 1： 输入：[2,7,4,1,8,1] 输出：1 解释： 先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]； 再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]； 再选出 2 和 1，得到 1，所以数组转换为 [1,1,1]； 再选出 1 和 1，得到 0，所以数组转换为 [1]； 最后剩下 1，返回 1。

提示： 1 <= stones.length <= 30 1 <= stones[i] <= 1000

二、算法原理

什么是优先级队列（堆）

优先级队列（Priority Queue）是一种特殊的队列，队列中的元素不再遵循'先进先出'的规则，而是按照元素的优先级决定出队顺序（优先级高的先出队）。

在 C++ 中，标准库的 priority_queue 默认是大顶堆（最大值优先级最高，堆顶是队列中的最大值），底层通常用完全二叉树实现，核心操作的时间复杂度为 O(log n)：

• 插入元素：O(log n)
• 删除堆顶元素：O(log n)
• 获取堆顶元素：O(1)

C++ priority_queue 常用接口

接口	功能
priority_queue<int> pq;	定义一个存储 int 类型的大顶堆（默认）
pq.push(x);	将元素 x 插入堆中，自动调整堆结构
pq.top();	获取堆顶元素（最大值），不删除
pq.pop();	删除堆顶元素，自动调整堆结构
pq.size();	获取堆中元素的个数
pq.empty();	判断堆是否为空

本题解题思路

本题的核心算法是 '大顶堆 + 模拟'：用大顶堆存储所有石头重量，每次取出堆顶的两个最大值（最重的两块石头），按规则处理后将剩余重量重新入堆，直到堆中只剩 0 或 1 个元素。

1. 初始化一个大顶堆，将所有石头的重量入堆。
2. 当堆中元素数量大于 1 时，执行以下操作：
   • 取出堆顶元素 a（当前最重的石头），并删除堆顶。
   • 取出新的堆顶元素 b（当前第二重的石头），并删除堆顶。
   • 计算两块石头的重量差 diff = a - b：
     • 若 diff > 0，将 diff 入堆（剩余的石头重量）；
     • 若 diff = 0，两块石头完全粉碎，无需入堆。
3. 遍历结束后：
   • 若堆为空，返回 0；