SlidingWindow { public static double[] medianSlidingWindow(int[] nums, int k) { if (nums == null || nums.length == 0) return new double[0]; double[] result = new double[nums.length - k + 1]; PriorityQueue<Integer> minQueue = new PriorityQueue<>(); PriorityQueue<Integer> maxQueue = new PriorityQueue<Integer>(Comparator.comparing(Integer::intValue).reversed()); for (int i = 0; i < nums.length; i++) { if (i - k >= 0) { int d = nums[i - k]; if (!minQueue.remove(d)) { maxQueue.remove(d); } } while (maxQueue.size() > minQueue.size() + 1) { minQueue.add(maxQueue.poll()); } while (minQueue.size() > maxQueue.size() + 1) { maxQueue.add(minQueue.poll()); } if (minQueue.isEmpty() || minQueue.peek() < nums[i]) { minQueue.add(nums[i]); } else { maxQueue.add(nums[i]); } while (maxQueue.size() > minQueue.size() + 1) { minQueue.add(maxQueue.poll()); } while (minQueue.size() > maxQueue.size() + 1) { maxQueue.add(minQueue.poll()); } int n = i + 1 - k; if (n >= 0) { if (minQueue.size() > maxQueue.size()) { result[n] = minQueue.peek(); } else if (minQueue.size() < maxQueue.size()) { result[n] = maxQueue.peek(); } else { result[n] = ((double) minQueue.peek() + (double) maxQueue.peek()) / 2.0; } } } return result; }  static int[] maxSlidingWindow(int[] nums, int k); String minWindowOrdered(String S, String T); String minWindowUnordered(String s, String t); static double[] medianSlidingWindow(int[] nums, int k);  }
@Test(dataProvider = "medSlideWindosDP") public void testMed(int[] nums, int k, double[] medWindows) { double[] actual = SlidingWindow.medianSlidingWindow(nums, k); assertEquals(actual, medWindows, String.format("actual = %s, expected = %s", DoubleStream.of(actual).mapToObj(String::valueOf).collect(joining(",", "[", "]")), DoubleStream.of(medWindows).mapToObj(String::valueOf).collect(joining(",", "[", "]")) )); }