滑动窗口中位数最优解

给定一个包含 n 个整数的数组，和一个大小为 k 的滑动窗口,从左到右在数组中滑动这个窗口，找到数组中每个窗口内的中位数。(如果数组个数是偶数，则在该窗口排序数字后，返回第 N/2 个数字。)

样例

对于数组 [1,2,7,8,5], 滑动大小 k = 3 的窗口时，返回 [2,7,7]

最初，窗口的数组是这样的：

[ | 1,2,7 | ,8,5] , 返回中位数 2;

接着，窗口继续向前滑动一次。

[1, | 2,7,8 | ,5], 返回中位数 7;

接着，窗口继续向前滑动一次。

[1,2, | 7,8,5 | ], 返回中位数 7;

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];

            // 让maxHeap始终保存小于一半的值，minHeap保存大于一半的，正好两半

            if( maxHeap.size() == 0 || maxHeap.peek() >= num)

                maxHeap.add(num);

            else minHeap.add(num);

            // 维护两个堆，保证两个堆得大小，要么保持一致（偶数时），要么maxHeap多一个（奇数时）

            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);

                // 维护两个堆，保证两个堆得大小，要么保持一致（偶数时），要么maxHeap多一个（奇数时）

                if( minHeap.size() > maxHeap.size() )

                    maxHeap.add(minHeap.poll());

                if( maxHeap.size() > minHeap.size() + 1 )

                    minHeap.add(maxHeap.poll());

            }

        }

        return res;

    }

}