1046. 最后一块石头的重量 Easy

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 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]，这就是最后剩下那块石头的重量。

解题思路

输入： 整数数组 stones，表示每块石头的重量。

输出： 最后剩下的一块石头的重量（若没有则返回 0）。

方法分析

• 这个“每次取最大值”的操作非常适合使用 最大堆（Max Heap）。
• 我们可以使用 最大堆（Max Heap） 来降低复杂度。

具体做法

1. 将所有石头放入最大堆中：
   • Python 中的 heapq 是最小堆，我们可以将元素取负来模拟最大堆。
   • 在 JavaScript 中则需要自定义 MaxHeap。
2. 循环执行相撞过程：
   • 每次取出堆顶的两块最重石头 y、x（其中 y ≥ x）。
   • 若两者重量不同，则将差值 y - x 再放回堆中。
   • 若两者相等，则两块石头都消失。
3. 结束条件：
   • 当堆中只剩下一块或为空时停止。
   • 若堆中还有石头，返回堆顶重量；否则返回 0。

复杂度分析

• 每次取出 / 插入堆的操作复杂度为 O(log n)。
• 一共最多进行 n - 1 次相撞操作。
• 因此总时间复杂度为： O(n log n)
• 堆中最多保存 n 个元素： 空间复杂度：O(n)

代码实现

python

import heapq

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        """
        思路：
        Python 的 heapq 是最小堆，我们可以取反（变成负数）来模拟最大堆。
        每次取出两个最大的石头，计算它们的差（若不相等则把差放回堆中）。
        最后堆中剩下的就是最后一块石头的重量（或空则返回 0）。
        """

        # 将所有石头取反以模拟最大堆
        stones = [-s for s in stones]
        heapq.heapify(stones)  # 建堆 O(n)

        # 当堆中石头数量大于 1 时，不断取出最重的两块石头
        while len(stones) > 1:
            # 取出两块最重的石头（注意取反）
            y = -heapq.heappop(stones)  # 最重
            x = -heapq.heappop(stones)  # 次重

            # 如果两块石头不相等，把差值放回堆中
            if x != y:
                heapq.heappush(stones, -(y - x))
            
        # 若堆不为空，返回最后一块石头的重量；否则返回 0
        return -stones[0] if stones else 0

javascript

var lastStoneWeight = function(stones) {
    // 使用自定义的最大堆（MaxHeap）
    const heap = new MaxHeap();

    // 把所有石头放入堆中
    for (const x of stones) heap.insert(x);

    // 每次取出两块最重的石头
    while (heap.size() > 1) {
        const y = heap.pop(); // 最重
        const x = heap.pop(); // 次重

        const diff = y - x;
        // 如果两块石头不相等，把剩余的差值重新放回堆
        if (diff > 0) heap.insert(diff);
    }

    // 返回堆中最后一块石头的重量（或 0）
    return heap.size() === 1 ? heap.pop() : 0;
};

复杂度分析

时间复杂度：O(nlogn)

空间复杂度：O(n)

链接

1046 国际版

1046 中文版