For every window of k consecutive numbers in nums, report its median. The window starts at the left and moves right one position at a time. Return the array of medians.
- For an odd
k the median is the middle number of the sorted window - For an even
k it is the average of the two middle numbers (so it can end in .5) 1 <= k <= nums.length. The numbers can be negative and can repeat, and can be as large as 2147483647- Sorting every window is O(n k log k). Aim for O(n log n) with two heaps and lazy deletion: a number that leaves the window is only marked dead, and is removed for real when it reaches the top of its heap
- A comparator-based
Heap class is already written for you