最后一块石头的重量

发表于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

LeetCode每日一题，1046. Last Stone Weight

先看题目描述

rqoxSJ.png

大意就是给定一个数组代表许多石头的重量，每次我们选最重的两个石头来相撞，设这两个石头的重量分别为 x 和 y 且 x <= y，若 x 和 y 相等，则这两个石头都被撞毁，若 x 小于 y，则会得到一个新的重量为 y - x 的石头，最后将会剩下至多一个石头，若没有石头则返回 0，若有一个石头则让我们返回该石头的重量

算法和思路

由于题目中说了每次都选出最重的两个石头进行相撞，且要将相撞后得到的新石头添加到石头集合中，我们很快就想到用一个最大堆来维护石头集合，最大堆会帮助我们自动维护石头集合按照降序排列。我们每次从最大堆中取出重量最大的两个石头，然后将这两个石头相撞，将产生的新石头再添加到最大堆中，即使取出的两个石头重量相等也没关系，我们视产生的新石头重量为 0，添加到最大堆中，由于该石头重量为 0，且会置于堆底，对我们的最终结果其实并不会产生影响

具体到实现上，算法流程如下：

  • 求得数组 stones 的长度 len，将 stones 中的所有元素添加到最大堆中
  • 执行如下循环 len -1 次：
    • 取出最大堆的前两个元素 x 和 y，然后将 x - y 放入最大堆中
  • 此时堆顶元素即我们要求的结果，将其返回

算法源码

最大堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int lastStoneWeight(int[] stones) {
        int len = stones.length;
        PriorityQueue<Integer> prior = new PriorityQueue<>((a, b) -> b - a);
        for (int stone : stones) {
            prior.add(stone);
        }
        for (int i = 1; i < len; i++) {
            int x = prior.poll();
            int y = prior.poll();
            prior.add(x - y);
        }
        return prior.poll();
    }
}

这里构造最大堆用了简化的写法，在参数中用 new Comparator() 重写 compare() 方法也同样可以构造最大堆，但感觉这种简化的写法运行效率更高些

ps：不知道为什么，用 prior.add() 方法的速度比 prior.offer() 方法要快些