Sliding Window Median

Given an array of n integer, and a moving window(size k), move the window at each iteration from the start of the array, find the median of the element inside the window at each moving. (If there are even numbers in the array, return the N/2-th number after sorting the element in the window. )

For array [1,2,7,8,5], moving window size k = 3. return [2,7,7] At first the window is at the start of the array like this [ | 1,2,7 | ,8,5] , return the median 2; then the window move one step forward. [1, | 2,7,8 | ,5], return the median 7; then the window move one step forward again. [1,2, | 7,8,5 | ], return the median 7;

提示里面说到O(nlgn)的复杂度，加上求median，很自然地会想到用heap。关于如何用两个堆track中位数很多文章里都有解释。问题是heap不支持random remove操作，如果自己实现会比较麻烦。java中PriorityQueue是支持random remove的，所以就偷懒使用了；如果在面试中可以自己解释如何实现这个机制。 根据题意，median总是取N/2向下取整的，所以只要一直保持maxheap的size不小于minheap的size，这样每次只要取maxheap的堆顶。 另外要注意的是每次remove之后可能会造成两个heap的size不平衡，所以要重新resize

public ArrayList<Integer> medianSlidingWindow(int[] nums, int k) {
        // write your code here
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(nums==null || nums.length==0 || k==0) return res;
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, Collections.reverseOrder());
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(k);

        for(int i=0; i<nums.length; i++){
            if(maxHeap.isEmpty() || nums[i]<maxHeap.peek()){
                maxHeap.add(nums[i]);
            }else{
                minHeap.add(nums[i]);
            }

            if(minHeap.size() > maxHeap.size()){
                maxHeap.add(minHeap.poll());
            }

            if(maxHeap.size() > minHeap.size()+1){
                minHeap.add(maxHeap.poll());
            }

            if(i>=k-1){
                res.add(maxHeap.peek());
                int toRemove = nums[i-k+1];
                if(toRemove<=maxHeap.peek()){
                    maxHeap.remove(toRemove);
                }else{
                    minHeap.remove(toRemove);
                }
                if(minHeap.size() > maxHeap.size()){
                    maxHeap.add(minHeap.poll());
                }
                if(maxHeap.size() > minHeap.size()+1){
                    minHeap.add(maxHeap.poll());
                }
            }
        }

        return res;
 }