题目描述

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

每一回合，从中选出两块最重的石头，然后将它们一起粉碎。假设两块石头的重量分别为 x 和 y，且 x <= y：

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

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

例如：stones = [2,7,4,1,8,1]

  • 第一轮：选出 8 和 7，剩下 8-7=1，数组变为 [2,4,1,1,1]
  • 第二轮：选出 4 和 2，剩下 4-2=2，数组变为 [2,1,1,1]
  • 第三轮：选出 2 和 1，剩下 2-1=1，数组变为 [1,1,1]
  • 第四轮：选出 1 和 1，完全粉碎，数组变为 [1]
  • 返回 1

解题思路

这道题完美适合使用最大堆（优先队列）来求解。因为每一轮都需要快速获取最大的两个元素，并在可能的情况下将差值插回。

大顶堆解法

  1. 将所有石头重量插入最大堆中。
  2. 当堆中元素数量 > 1 时，循环执行：
    • 取出最大的元素 max1（堆顶）。
    • 再取出次大的元素 max2。
    • 如果 max1 != max2，将差值 abs(max1 - max2) 插回堆中。
    • 如果 max1 == max2，两块石头都销毁，无需插回。
  3. 循环结束后：
    • 如果堆为空，返回 0；
    • 否则返回堆中仅剩的一个元素。

注：代码中使用了自定义的 MyMaxHeap 数据结构，其功能等价于 java.util.PriorityQueue 配合 Collections.reverseOrder()（或者直接用负数存入小顶堆来模拟大顶堆）。

为什么用最大堆？

每一轮需要获取”最大的两个数”，最大堆可以在 O(log n) 时间内完成取出最大元素和插入新元素的操作。如果每次都对数组排序或扫描查找最大元素，时间复杂度会达到 O(n² log n) 或 O(n²)，在大数据量下不可接受。

复杂度分析

  • 时间复杂度：O(n log n)，其中 n 是石头数量。每轮操作（两次取出 + 一次插入）需要 O(log n)，最多进行 n-1 轮。
  • 空间复杂度：O(n)，最大堆需要存储所有石头重量。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package code.J1046;

import datastructure.MyMaxHeap;

public class J046 {
    public int lastStoneWeight(int[] stones) {
        MyMaxHeap<Integer> myMaxHeap = new MyMaxHeap<>(stones.length);
        for (int stone : stones) {
            myMaxHeap.insert(stone);
        }
        while (myMaxHeap.size() > 1) {
            int max1 = myMaxHeap.extractMax();
            int max2 = myMaxHeap.extractMax();
            if (max1 != max2) {
                myMaxHeap.insert(Math.abs(max1 - max2));
            }
        }
        if (myMaxHeap.isEmpty()) return 0;
        return myMaxHeap.extractMax();
    }
}