1
class Solution {
2
  public double[] medianSlidingWindow(int[] nums, int k) {
3
    Queue<Integer> minHeap = new PriorityQueue<>();
4
    Queue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
5

6
    double[] res = new double[nums.length - k + 1];
7
    for (int i = 0; i < nums.length; i++) {
8
      if (i >= k) {
9
        if (!minHeap.remove(nums[i - k])) maxHeap.remove(nums[i - k]);
10
      }
11

12
      // If k is odd, max heap is of odd size and min heap is of even
13
      // else both are of even size
14
      if (!maxHeap.isEmpty() && nums[i] <= maxHeap.peek()) {
15
        maxHeap.add(nums[i]);
16
        if (((k & 1) == 1 && maxHeap.size() > k / 2 + 1)
17
            || ((k & 1) == 0 && maxHeap.size() > k / 2)) {
18
          minHeap.offer(maxHeap.poll());
19
        }
20
      } else {
21
        minHeap.add(nums[i]);
22
        if (minHeap.size() > k / 2) {
23
          maxHeap.offer(minHeap.poll());
24
        }
25
      }
26
      while (!minHeap.isEmpty() && !maxHeap.isEmpty() && maxHeap.peek() > minHeap.peek()) {
27
        int temp1 = maxHeap.poll();
28
        int temp2 = minHeap.poll();
29
        maxHeap.add(temp2);
30
        minHeap.add(temp1);
31
      }
32
      if (minHeap.size() + maxHeap.size() == k) {
33
        if ((k & 1) == 1) {
34
          res[i - k + 1] = maxHeap.peek();
35
        } else {
36
          res[i - k + 1] = ((long) minHeap.peek() + (long) maxHeap.peek()) / 2.0;
37
        }
38
      }
39
    }
40
    return res;
41
  }
42
}