一、題目

有一堆石頭，每塊石頭的重量都是正整數。

每一回合，從中選出兩塊?最重的?石頭，然后將它們一起粉碎。假設石頭的重量分別為?x?和?y，且?x <= y。那么粉碎的可能結果如下：

• 如果?x == y，那么兩塊石頭都會被完全粉碎；
• 如果?x != y，那么重量為?x?的石頭將會完全粉碎，而重量為?y?的石頭新重量為?y-x。

最后，最多只會剩下一塊石頭。返回此石頭的重量。如果沒有石頭剩下，就返回?0。

示例：

輸入：[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]，這就是最后剩下那塊石頭的重量。

提示：

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

二、思路解析

這道題要用到 “大根堆” 這個容器來解決，因為大根堆可以快速幫我們把元素排序成升序狀態。

然后就要讓兩個堆頂元素比較大小，看看能否粉碎。

有一個細節，因為 a 是在 b 之前的堆頂元素，所以 a 只可能是大于或等于 b ，而不可能是小于。

所以在判斷他們二者大小的時候，我們只需要討論 a > b 的情況即可，然后把差值 a - b 插入大根堆。

具體實現請看下面代碼👇

三、完整代碼

class Solution {public int lastStoneWeight(int[] stones) {PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);for(int x : stones){heap.offer(x);}while(heap.size() > 1){int a = heap.poll();int b = heap.poll();if(a > b){heap.offer(a - b);}}return heap.isEmpty() ? 0 : heap.peek();}
}

以上就是本篇博客的全部內容啦，如有不足之處，還請各位指出，期待能和各位一起進步！