1046. 最后一块石头的重量

1、题目描述

2、题目解析

因为每一回合都要选出【最重的两块石头】，因此每次都需要排序，可以联想到使用现成能够自动排序的数据结构，因此 想到【堆】这个可以自动实现排序的数据结构。

将所有的石头放入到大顶堆中，然后依次取出最重的两块石头x和y，必有x ≥ y。如果x > y，则将新石头x - y放回到最大堆中；如果x = y,两块石头完全被粉碎，因此不会产生新的石头。

• 用【JAVA】实现，声明 【降序】 的大根堆是难点：
• PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);

实现代码如下：

class Solution {
    public int lastStoneWeight(int[] stones) {
        //申明大根堆，避免每次都进行排序
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a,b)->b-a);
        for(int stone : stones){
            pq.offer(stone);
        }

        while(pq.size() > 1){
            //由于pq之前已经对数组进行排序，每次拿最大的两个数，只存在 b<=a的可能
            int a = pq.poll();
            int b = pq.poll();
            //b=a时，两个直接poll即可，当b<a时，需要再往堆中写入（b-a）这个数字
            if(b < a){
                pq.offer(a-b);
            }
        }
        return pq.isEmpty() ? 0:pq.poll();
    }
}

复杂度分析

时间复杂度：O(nlogn)，其中 n 是石头数量。每次从队列中取出元素需要花费 O(logn) 的时间，最多共需要粉碎 n−1 次石头。

空间复杂度：O(n)。