leetcode - [1046] Last Stone Weight

2020/09/14

问题描述

We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together. 
Suppose the stones have weights x and y with x <= y.  The result of this smash is:

  • If x == y, both stones are totally destroyed;
  • If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left.  Return the weight of this stone (or 0 if there are no stones left.)

提供一个整数数组,每个元素代表一块石头的重量。

每次从中挑选两块最重的石头然后将其粉碎,假设x <= y,粉碎规则如下:

  • 如果x == y,那么两块石头均被完全粉碎。
  • 如果x != y,那么轻的那块石头x就会被完全粉碎,而重量为y的石头变成y - x

最后,最多会剩下一块石头,请返回其最小重量(如果没有石头剩下,则返回0)。

举个例子:

解法1

Thanks
@rock
@wzc1995

思路是这样的:

使用一个最大堆存储所有元素,然后每次取头两个元素,

若相等,则直接进行下一次遍历,否则将差值(正整数)重新加入最大堆,直至堆中还剩一个元素。

来看下实现:


class Solution {
    public int lastStoneWeight(int[] stones) {
        
        var maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());
        for (int s: stones){
            maxHeap.offer(s);
        }

        while (maxHeap.size() > 1){
            int a = maxHeap.poll();
            int b = maxHeap.poll();
            int diff = Math.abs(a - b);
            if (diff > 0){
                maxHeap.offer(diff);
            }
        }
        return maxHeap.isEmpty() ? 0 : maxHeap.peek();
    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory