2018-08-14 LeetCode数据流的中位数

较小的一半数放在大根堆较大的在小根堆，大根堆堆顶为较小数的最大值，小根堆的堆顶为较大数的最小值
始终保持大根堆和小根堆size相等或者大根堆比小根堆多一

class MedianFinder {
    PriorityQueue<Integer> minQueue;
    PriorityQueue<Integer> maxQueue;
    /** initialize your data structure here. */
    public MedianFinder() {
        minQueue = new PriorityQueue();
        maxQueue = new PriorityQueue(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {                
                return o2-o1;
            }
        });//Collections.reverseOrder()//(o1,o2)->o2-o1
    }

    public void addNum(int num) {
        if(maxQueue.isEmpty() ||num <= maxQueue.peek()){
            maxQueue.offer(num);
        }else{
            minQueue.offer(num);
        }
        if(maxQueue.size() < minQueue.size()){
            maxQueue.offer(minQueue.poll());
        }else if(maxQueue.size() > minQueue.size() + 1){
            minQueue.offer(maxQueue.poll());
        }
    }

    public double findMedian() {
        if(maxQueue.size() == 0 && minQueue.size() == 0)return 0;
        if(maxQueue.size() == minQueue.size()){
            return (maxQueue.peek() + minQueue.peek()) / 2.0;
        }else{
            return maxQueue.peek();
        }
    }
}

public class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int m = n - k + 1; 
        double[] res = new double[m];
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, Collections.reverseOrder());
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(k);
        for ( int i=0; i<n; i++){
            int num = nums[i];
            if( maxHeap.size() == 0 || maxHeap.peek() >= num)
                maxHeap.add(num);
            else minHeap.add(num);
            if( minHeap.size() > maxHeap.size() )
                maxHeap.add(minHeap.poll());
            if( maxHeap.size() > minHeap.size() + 1 )
                minHeap.add(maxHeap.poll());
            if ( i-k+1 >=0 ){
                if( k % 2 == 1 )
                    res[i- k + 1] = maxHeap.peek();
                else 
                    res[i- k + 1] = (maxHeap.peek()/2.0 + minHeap.peek()/2.0); 
                int toBeRemove = nums[i - k + 1];
                if( toBeRemove <= maxHeap.peek())
                    maxHeap.remove(toBeRemove);
                else minHeap.remove(toBeRemove);
                if( minHeap.size() > maxHeap.size() )
                    maxHeap.add(minHeap.poll());
                if( maxHeap.size() > minHeap.size() + 1 )
                    minHeap.add(maxHeap.poll());
            }
        }
        return res;
    }
}