class Solution { public int lastStoneWeight(int[] stones) { MaxHeap s=new MaxHeap(stones.length+1); for(int i=0;i<stones.length;i++) { s.insert(stones[i]); } while(s.size()>1) { int y=s.extractMax(); int x=s.extractMax(); if(y>x) { s.insert(y-x); } } if(s.size()==1) { return s.extractMax(); } else return 0; }}class MaxHeap{ private int[] stone; private int count; private int capacity; public MaxHeap(int capacity) { this.capacity=capacity; stone=new int[capacity+1]; count=0; } public void insert(int n) { stone[++count]=n; shiftUp(count); } private void shiftUp(int count) { while(count>1&&stone[count/2]<stone[count]) { swap(count/2,count); count=count/2; } } public void swap(int i,int j) { int temp=stone[i]; stone[i]=stone[j]; stone[j]=temp; } public int extractMax() { int res=stone[1]; swap(1,count); count--; shiftDown(1); return res; } private void shiftDown(int i) { int j=2*i; while(j<=count) { if(j+1<=count&&stone[j+1]>stone[j]) { if(stone[j+1]>stone[i]) { swap(j+1,i); i=j+1; j=2*i; } else break; } else { if(stone[j]>stone[i]) { swap(j,i); i=j; j=2*i; } else break; } } } public int size() { return count; }}
转载于:https://www.cnblogs.com/cold-windy/p/11201338.html
