【LeetCode 1046】最后一块石头的重量

题目描述：
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块最重的石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

提示：
1 <= stones.length <= 30
1 <= stones[i] <= 1000

题解：
首先先用堆排序把数组初始化为最大堆排序，这样堆顶元素就是重量最大的石头，然后选出数组的第二大元素与堆顶元素进行相减，小的石头重量置为0，堆顶元素的值置为相减后的数值。之后每一趟再重新构造为最大堆，这样就可以确保堆顶元素始终为重量最大的石头。

class Solution {
    public int lastStoneWeight(int[] stones) {
    int len=stones.length;if(len==1)return stones[0];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; //最大堆的堆顶元素与第二大元素的差值重新赋值给堆顶元素//与最大值相减后置0if(stones[1]>stones[2])stones[1]=0;elsestones[2]=0;for(int i=2;i>=0;i--){
      //每一趟循环3次重新构造最大堆，每一趟确保数组前三个是整个数组前3大的元素maxHeap(stones,i,len-1);}}return stones[0];  //返回堆顶元素}  }//调整最大堆public void maxHeap(int [] stones,int start,int end){
    int current=start;   //当前结点为currentint left=current*2+1;   //左孩子int temp=stones[current];  //当前节点current的值for(;left<=end;current=left,left=left*2+1){
      //跳出条件是left<=endif(left<end && stones[left]<stones[left+1])left++;  //左右孩子中选择最大值if(temp>=stones[left])break;else{
    stones[current]=stones[left];  //左右孩子中最大值与当前current调整交换stones[left]=temp;}}}
}