问题描述

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{:target=”_blank”}
@wzc1995{:target=”_blank”}

思路是这样的：

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

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

来看下实现：

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 !