Easy

题目描述

给你一个整数数组 stones，其中 stones[i] 表示第 i 块石头的重量。

我们用这些石头来玩一个游戏。每一回合，我们选择最重的两块石头并将它们相撞。假设最重的两块石头的重量分别为 x 和 y，且 x <= y。那么相撞的结果如下：

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

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

示例 1：

输入：stones = [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]，这就是最后剩下的石头重量。

示例 2：

输入：stones = [1]
输出：1

约束条件：

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 1000

解题思路

这道题要求我们模拟石头相撞的过程，每次选择最重的两块石头进行相撞。

有两种主要思路：

  1. 最大堆（推荐）：使用优先队列（最大堆）维护石头重量，每次取出两个最大的元素进行相撞。如果相撞后还有剩余重量，就将结果重新放入堆中。这种方法效率最高。

  2. 排序法：每次都对数组重新排序，取出最大的两个元素进行计算。虽然思路简单，但时间复杂度较高。

使用最大堆的优势在于：

  • 自动维护元素的大小顺序
  • 插入和删除操作都是 O(log n) 时间复杂度
  • 代码简洁清晰

算法流程：

  1. 将所有石头重量加入最大堆
  2. 当堆中元素个数大于1时，取出最重的两块石头
  3. 计算相撞后的结果，如果有剩余重量就重新加入堆中
  4. 重复直到堆中最多只剩一个元素
  5. 返回最后剩余的石头重量（如果没有则返回0）

代码实现

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq(stones.begin(), stones.end());
        
        while (pq.size() > 1) {
            int first = pq.top(); pq.pop();
            int second = pq.top(); pq.pop();
            
            if (first != second) {
                pq.push(first - second);
            }
        }
        
        return pq.empty() ? 0 : pq.top();
    }
};

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        import heapq
        
        # Python的heapq是最小堆，所以我们存储负值来模拟最大堆
        heap = [-stone for stone in stones]
        heapq.heapify(heap)
        
        while len(heap) > 1:
            first = -heapq.heappop(heap)
            second = -heapq.heappop(heap)
            
            if first != second:
                heapq.heappush(heap, -(first - second))
        
        return -heap[0] if heap else 0

public class Solution {
    public int LastStoneWeight(int[] stones) {
        var pq = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        
        foreach (int stone in stones) {
            pq.Enqueue(stone, stone);
        }
        
        while (pq.Count > 1) {
            int first = pq.Dequeue();
            int second = pq.Dequeue();
            
            if (first != second) {
                pq.Enqueue(first - second, first - second);
            }
        }
        
        return pq.Count == 0 ? 0 : pq.Peek();
    }
}

var lastStoneWeight = function(stones) {
    while (stones.length > 1) {
        stones.sort((a, b) => b - a);
        const first = stones.shift();
        const second = stones.shift();
        if (first !== second) {
            stones.push(first - second);
        }
    }
    return stones.length === 1 ? stones[0] : 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型最大堆解法排序解法
时间复杂度O(n log n)O(n² log n)
空间复杂度O(n)O(1)

说明：

  • 最大堆解法：初始建堆 O(n)，最多进行 n-1 次操作，每次操作包含两次弹出和最多一次插入，每个操作 O(log n)
  • 排序解法：每次相撞后都需要重新排序，最坏情况下需要 O(n) 次排序，每次排序 O(n log n)