1046. 最后一块石头的重量

🎯 问题描述

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

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

说明：

这是一个典型的堆(优先队列)应用问题。
核心策略：
- 题目要求每次都要取出当前“最大”的两个元素，这正是最大堆（大根堆）最擅长的操作。
- 由于 Python 的 heapq 模块默认只提供最小堆，我们可以通过将所有石头重量取相反数（负数）存入堆中，从而巧妙地模拟出最大堆的效果。
- 每次从堆中取出两个最小的负数（即绝对值最大的两个正数）进行碰撞，再将差值的负数放回堆中。
示例：
示例 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：最大堆（优先队列）模拟

核心逻辑

构建最大堆：
- 遍历 stones 数组，将所有石头的重量取相反数（-num），存入列表 nums 中。
- 使用 heapq.heapify(nums) 将列表原地转换为最小堆。由于存的是负数，堆顶元素（最小的负数）对应的就是原始数据中最大的正数。
模拟碰撞过程：
- 只要堆中的石头数量大于 1，就持续进行碰撞。
- 每次从堆顶弹出两个元素 x 和 y（它们是当前堆中最小的两个负数，即最重的两块石头）。
- 计算碰撞后的结果：由于 x 和 y 都是负数，x - y 的结果正好等于两块石头重量差值的相反数（假设 abs(x) >= abs(y)）。
- 将计算结果 x - y 重新压入堆中。如果两块石头重量相等，x - y 为 0，压入 0 对最终结果没有影响（或者也可以选择不压入）。
返回结果：
- 循环结束后，堆中最多只剩一个元素。弹出该元素并取相反数返回。如果堆为空（这种情况在代码中通过最后的 pop 处理），则返回 0。

代码实现

import heapq
from typing import List

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # 1. 将所有石头重量取反，构建最小堆来模拟最大堆
        nums = [-num for num in stones]
        heapq.heapify(nums)
        
        # 2. 只要堆中石头数量大于1，就持续碰撞
        while len(nums) > 1:
            # 弹出两个最小的负数（即最重的两块石头）
            x = heapq.heappop(nums)
            y = heapq.heappop(nums)
            # 碰撞后，将差值的负数重新压入堆中
            # 因为 x, y 都是负数，x - y 等价于 -(abs(x) - abs(y))
            heapq.heappush(nums, x - y)
        
        # 3. 返回最后剩下的石头重量（取反还原）
        # 如果堆为空，heappop 会报错，但根据题目逻辑，循环结束后堆里至少有一个元素（可能是0）
        return -heapq.heappop(nums)

📊 性能分析

时间复杂度：O(N log N)
- 构建堆的时间复杂度为 O(N)。
- 每次 heappop 和 heappush 操作的时间复杂度为 O(log N)。
- 在最坏情况下，我们最多需要进行 N-1 次碰撞操作，因此总体时间复杂度为 O(N log N)。
空间复杂度：O(N)
- 需要一个额外的堆（列表）来存储 N 个石头的重量。

思考

为什么要用负数模拟最大堆？
- Python 的标准库 heapq 只实现了最小堆（堆顶始终是最小值）。
- 为了每次都能快速取出“最重”的石头（最大值），我们将所有数值取反。这样，原本最大的正数变成了最小的负数，正好位于堆顶，完美契合了题目的需求。
关于 x - y 的计算细节：
- 假设两块石头重量分别为 8 和 7，存入堆中为 -8 和 -7。
- heappop 取出的 x = -8, y = -7。
- 碰撞后的新重量应为 8 - 7 = 1。
- 代码中计算 x - y = (-8) - (-7) = -1。
- 将 -1 压入堆中，正好对应了新重量 1 的负数形式。这个数学技巧让代码极其简洁。
边界情况：
- 如果输入只有一个石头，while 循环不会执行，直接弹出并返回该石头的重量。
- 如果所有石头都完全粉碎（例如 [1, 1]），堆中最后会剩下一个 0（因为 -1 - (-1) = 0），最后返回 -0 即 0，符合题目要求。
与其他解法的对比：
- 也可以使用数组每次排序（sort）来取最大值，但每次排序的时间复杂度是 O(N log N)，总复杂度会达到 O(N² log N)，效率远低于堆解法。