Sliding Window Median

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples: [2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.

For example, Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Median
---------------               -----
[1  3  -1] -3  5  3  6  7       1
 1 [3  -1  -3] 5  3  6  7       -1
 1  3 [-1  -3  5] 3  6  7       -1
 1  3  -1 [-3  5  3] 6  7       3
 1  3  -1  -3 [5  3  6] 7       5
 1  3  -1  -3  5 [3  6  7]      6

Therefore, return the median sliding window as [1,-1,-1,3,5,6].

Note: You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

Tips:

建一个最大堆一个最小堆，最大堆存放小的数最小堆存放大的数，二者堆顶的平均值即为这个区间的median。 注意时刻更新两个堆，保持最小堆的大小始终为最大堆的大小或最大堆+1。有新数加入时先删除再入堆。 注意(double)的用法，不然达到Integer.MAX_VALUE的时候回报错。 注意重写的compare方法要用Integer和compareTo,直接用int和-不对，会遇到int最大值会出错。

Code:

public class Solution {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
        public int compare(Integer a, Integer b) {
            return b.compareTo(a);
        }
    });
    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length - k + 1;
        if (n <= 0) return new double[0];
        double[] res = new double[n];
        for (int i = 0; i <= nums.length; i++) {
            if (i >= k) {
                res[i - k] = getMedian();
                remove(nums[i - k]);
            }
            if (i < nums.length) {
                add(nums[i]);
            }
        }
        return res;
    }
    private double getMedian() {
        if (minHeap.isEmpty() && maxHeap.isEmpty()) return 0;
        if (minHeap.size() == maxHeap.size()) return ((double)maxHeap.peek() + (double)minHeap.peek())/2.0;
        else return (double)minHeap.peek();
    }
    private void remove(int x) {
        if (x < getMedian()) maxHeap.remove(x);
        else minHeap.remove(x);
        if (maxHeap.size() > minHeap.size()) minHeap.add(maxHeap.poll());
        if (minHeap.size() > maxHeap.size() + 1) maxHeap.add(minHeap.poll());        
    }
    private void add(int x) {
        if (x < getMedian()) maxHeap.add(x);
        else minHeap.add(x);
        if (maxHeap.size() > minHeap.size()) minHeap.add(maxHeap.poll());
        if (minHeap.size() > maxHeap.size() + 1) maxHeap.add(minHeap.poll());
    }
}