LeetCode1046-最后一块石头的重量

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/last-stone-weight/

中文链接：https://leetcode-cn.com/problems/last-stone-weight/

题目详述

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

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

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

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

提示：

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

题目详解

  • 因为每次选出两块最重的石头，可以构建一个大顶堆。
  • 每次取出堆顶的两个元素进行运算，直至堆的大小小于 2。
  • 如果堆为空返回 0，否则返回堆顶元素。
  • 时间复杂度为 O(nlogn)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LeetCode_01046 {

    public int lastStoneWeight(int[] stones) {
        Queue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
        for (int stone : stones) {
            queue.offer(stone);
        }
        while (queue.size() > 1) {
            int x = queue.poll();
            int y = queue.poll();
            if (x != y) {
                queue.offer(x - y);
            }
        }
        return queue.isEmpty() ? 0 : queue.poll();
    }
}