最后一块石头的重量

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

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

如果 x == y，那么两块石头都会被完全粉碎；

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

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

提示：

1 <= stones.length <= 30

1 <= stones[i] <= 1000

public class lastStoneWeight {
    public static void main(String[] args) {
        int[] stones = {2,7,4,1,8,1};
        lastStoneWeight(stones);
    }
    public static int lastStoneWeight(int[] stones) {
        if(stones == null){
            return 0;
        }
        if(stones.length< 2){
            return stones[0];
        }
        int length=stones.length;
        while(length>=2){
            Arrays.sort(stones);
            if(stones[length-2]==stones[length-1]) {
                length -= 2;
            }
            else{
                stones[length-2]=stones[length-1]-stones[length-2];
                length--;

            }
        }
        if(length==1) {
            return stones[0];
        }
        else {
            return 0;
        }
    }
}

堆排序

  • 初始化最大堆
  • 循环（直至Math.max(stones[1], stones[2])==0）
    • 按要求修改堆顶两个元素

重新调整最大堆

public int lastStoneWeight(int[] stones) {
    int len = stones.length;
    if (len==1) {
        return stones[0];
    }else if (len==2) {
        return Math.abs(stones[0]-stones[1]);
    }else {
        for (int i = len/2-1; i >= 0 ; i--) {
            maxHeap(stones, i, len-1);
        }
        int temp;
        while ((temp=Math.max(stones[1], stones[2]))!=0) {
            stones[0]-=temp;
            if (stones[1]>stones[2]) {
                stones[1]=0;
            }else {
                stones[2]=0;
            }
            for (int i = 2; i >= 0 ; i--) {
                maxHeap(stones, i, len-1);
            }
        }
        return stones[0];
    }
}
public void maxHeap(int[] nums, int root, int end) {
    int l=2*root+1;
    int temp=nums[root];
    while (l<=end && (nums[l]>temp || (l+1<=end && nums[l+1]>temp))) {
        if (l+1<=end && nums[l+1]>nums[l]) {
            l++;
        }
        nums[root]=nums[l];
        nums[l]=temp;
        root=l; l=2*root+1;
        temp=nums[root];
    }
}

使用现成的大顶堆

/**
     * java大顶堆
     * 执行用时 :43 ms, 在所有 Java 提交中击败了10.83%的用户
     * 内存消耗 :34.4 MB, 在所有 Java 提交中击败了100.00%的用户
     */
    public static int lastStoneWeight3(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((i1, i2) -> i2 - i1);
        for (int x: stones) {
            pq.offer(x);
        }
        while (pq.size() > 1) {
            int remaining = pq.poll() - pq.poll();
            if (remaining != 0) {
                pq.offer(remaining);
            }
        }
        return pq.isEmpty() ? 0 : pq.poll();
    }

双栈实现最大堆

/**
     * 双栈实现最大堆
     * 执行用时 : 7 ms, 在所有 Java 提交中击败了15.14%的用户
     * 内存消耗 :34 MB, 在所有 Java 提交中击败了100.00%的用户
     */
    public static int lastStoneWeight(int[] stones) {
        Stack<Integer> max = new Stack();
        Stack<Integer> temp = new Stack<>();
        for (int x: stones) {
            while (!max.isEmpty() && max.peek() > x) {
                temp.push(max.pop());
            }
            max.push(x);
            while (!temp.isEmpty()) {
                max.push(temp.pop());
            }
        }
        while (max.size() > 1) {
            int remaining = max.pop() - max.pop();
            if (remaining != 0) {
                while (!max.isEmpty() && max.peek() > remaining) {
                    temp.push(max.pop());
                }
                max.push(remaining);
                while (!temp.isEmpty()) {
                    max.push(temp.pop());
                }
            }
        }
        return max.isEmpty() ? 0 : max.pop();
    }
}