LeetCode之最后一块石头的重量

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

如果 x == y，那么两块石头都会被完全粉碎；如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。 示例： 提示： 方法一：优先队列 class Solution { public int lastStoneWeight(int[] stones) { int len=stones.length; PriorityQueue<Integer> max_Heap=new PriorityQueue<>(len,(o1,o2)->o2-o1); for(int stone:stones) { max_Heap.add(stone); } int max1,max2; while(max_Heap.size()>1) { max1=max_Heap.poll(); max2=max_Heap.poll(); if(max1-max2>0) { max_Heap.offer(max1-max2); } } return max_Heap.isEmpty()?0:max_Heap.poll(); } }

方法二：排序

class Solution { public int lastStoneWeight(int[] stones) { if (stones.length == 1) { return stones[0]; } Arrays.sort(stones); while (stones[stones.length - 2] != 0) { stones[stones.length - 1] = stones[stones.length - 1] - stones[stones.length - 2]; stones[stones.length - 2] = 0; Arrays.sort(stones); } return stones[stones.length - 1]; } }

方法三：栈

class Solution { public int lastStoneWeight(int[] stones) { Deque<Integer> deque = new LinkedList<>(); Deque<Integer> tempDeque = new LinkedList<>(); Arrays.sort(stones); for (int stone : stones) { deque.push(stone); } while (deque.size() > 1) { int newStone = deque.pop() - deque.pop(); while (deque.size() > 0 && deque.peek() > newStone) { tempDeque.push(deque.pop()); } deque.push(newStone); while (tempDeque.size() > 0) { deque.push(tempDeque.pop()); } } return deque.pop(); } }