SlidingWindowMedian.java

import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        int len = nums.length; 
        double[] result = new double[len - k + 1];
        Queue<Long> queue = new LinkedList<>(); 
        PriorityQueue<Long> maxHeap = new PriorityQueue<>(new Comparator<Long>() {
            @Override 
            public int compare(Long a, Long b) {
                if (b < a) return -1;
                else return 1;
            }
        }); 
        PriorityQueue<Long> minHeap = new PriorityQueue<>(); 
        int i = 0; 
        
        for (int n : nums) {
            queue.add((long)n);
            if (maxHeap.isEmpty() || n <= maxHeap.peek()) {
            	maxHeap.add((long)n);
            } else {
            	minHeap.add((long)n);
            }
            if (queue.size() > k) {
                long front = queue.remove(); 
                if (maxHeap.contains(front)) maxHeap.remove(front);
                else minHeap.remove(front);
            }
            
            while (maxHeap.size() > minHeap.size() + 1) {
                minHeap.add(maxHeap.remove());
            }
            
            while (minHeap.size() > maxHeap.size()) {
                maxHeap.add(minHeap.remove());
            }
            
            if (queue.size() < k) continue; 
            
            if (maxHeap.size() == minHeap.size()) {
                result[i] = (maxHeap.peek() + minHeap.peek()) / 2.0; 
            } else {
                result[i] = maxHeap.peek(); 
            }
            
            i++; 
        }
        
        return result; 
    }
}