LeetCode1046 最后一块石头的重量

Ted

发布于：2020年12月30日

次浏览

使用priority_queue解决最大堆问题。

1046. 最后一块石头的重量

题目描述

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

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

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
  最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

示例：

1
2
3
4
5
6
7

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

题目解析

这道题读完题后感觉并不是太难，只要对这堆石头，每次找出最大的两块然后敲碎，全部丢掉或者留下一块小石头继续就行了。可是我却很难想到一个高效的方法来解决这个问题。如果要使用一个有效的数据结构，那么这个结构要能保存一个按大小排列的数组，并在每次取出最大的两个数后，将可能剩下的一个数插入数组，并保持数组的有序性。如果每次都使用一次排序的话未免太复杂了些，如果使用之前刚刚学过的单调栈，又不能在敲碎两块石头后有效的处理剩下的一块石头。队列和栈看起来也不好处理这个问题。无奈之下只好再次求助答案，结果看到了“最大堆”这个说法，恍然大悟！

其实堆很久以前数据结构就学过，大致记得是一个以二叉树形式存储数据，使所有数据满足“父节点的数值大于子节点数值”的一个数据结构。在学排序的时候还学过堆排序，应该就是先构建一个堆，然后就很好排序了。不过说实话我早就忘记了怎么实现这个数据结构，看来之后还要好好复习一下。。。。。。不过我也不记得STL里面专门有heap这种类型的数据结构，所以虽然知道了大概的方法，但还是写不出来😂

又瞟了一眼别人答案的代码，一眼看到了一个奇怪的东西priority_queue，我寻思队列怎么跟堆也扯不上关系，为啥这个优先队列就行呢？结果一看优先队列的使用方式才发现，这个“优先”正是通过堆来实现的！

优先队列priority_queue通过与普通queue不同的地方就在于，队列中的数据优先级可以定义，并自动根据优先级排队，按照优先级顺序出队。其余入队、出队的方式就与queue一样了。底层由一个堆实现，默认是按照大根堆来实现的，也就是说，大的元素在最顶端。于是在这道题中，就可以将所有石块加入这个优先队列，这样他们就会自动按照从大到小的顺序排序，并在每次更新，加入新的石块时仍然保持排序不变。

按照概念自己瞎写了个代码，最终正确通过了，看来以后还是在刷题的同时要好好学习和复习数据结构方面的知识。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int>heap;
        // int stone = stones.size();
        for (int i = 0; i < stones.size(); i++) {
            heap.push(stones[i]);
        }
        while (heap.size() > 1) {
            int x = heap.top();
            heap.pop();
            int y = heap.top();
            heap.pop();
            if (x == y) continue;
            else {
                heap.push(x - y);
            }
        }
        if (!heap.empty()) return heap.top();
        else return 0;
    }
};

最后更新于：2020年12月29日

LeetCode

最大堆