480. Sliding Window Median

480. Sliding Window Median

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: k is always smaller than input array's size for non-empty array.

-------------------------------
类似295用2个priority queue
1. 记录maxQ和minQ里合法数值的数量，而不是queue大小，因为我们有sliding window
2. 每移动一次，要invalidate之前window最旧的那个，这时我们用一个额外数组来记录它属于哪个queue，同时那个queue的合法数值的数量可以 - 1
3. 每次从queue里出来的时候要检查当前的数值是否合法

class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        PriorityQueue<Pair> minQ = new PriorityQueue<>((a, b) -> ((Integer)a.val).compareTo(b.val)); // left
        PriorityQueue<Pair> maxQ = new PriorityQueue<>((a, b) -> ((Integer)b.val).compareTo(a.val)); // right

        int n = nums.length;
        boolean[] sides = new boolean[n]; // true - left, false - right

        PriorityQueue<Pair> tmp = new PriorityQueue<>((a, b) -> ((Integer)b.val).compareTo(a.val));
        for (int i = 0; i < k; i++) {
            tmp.add(new Pair(i, nums[i]));
        }

        for (int i = 0; i < k / 2; i++) {
            Pair p = tmp.poll();
            minQ.add(p);
        }

        while (!tmp.isEmpty()) {
            Pair p = tmp.poll();
            sides[p.index] = true;
            maxQ.add(p);
        }

        int countL = maxQ.size(), countR = minQ.size();
        double[] rt = new double[n - k + 1];
        if (countL > countR) rt[0] = maxQ.peek().val * 1.0;
        else rt[0] = minQ.peek().val / 2.0 + maxQ.peek().val / 2.0;

        for (int i = k; i < n; i++) {
            int inval = i - k;
            if (sides[inval]) countL--;
            else countR--;

            maxQ.add(new Pair(i, nums[i]));
            sides[i] = true;
            popInvalid(maxQ, inval);
            Pair cand = maxQ.poll();
            minQ.add(cand);
            sides[cand.index] = false;
            popInvalid(minQ, inval);
            cand = minQ.poll();

            if (countL <= countR) {
                maxQ.add(cand);
                countL++;
                sides[cand.index] = true;
            }else {
                minQ.add(cand);
                countR++;
                sides[cand.index] = false;
            }

            if (countL > countR) {
                popInvalid(maxQ, inval);
                rt[i - k + 1] = maxQ.peek().val * 1.0;
            } else {
                popInvalid(maxQ, inval);
                popInvalid(minQ, inval);
                rt[i - k + 1] = minQ.peek().val / 2.0 + maxQ.peek().val / 2.0;    
            }
        }

        return rt;
    }
    
    private void popInvalid(PriorityQueue<Pair> que, int bound) {
        while (!que.isEmpty() && que.peek().index <= bound) {
            que.poll();
        }
    }
    
    class Pair{
        public int index;
        public int val;
        public Pair(int index, int val) {
            this.index = index;
            this.val = val;
        }
    }
}