Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
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 knumbers 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.
idea:
最小堆+最大堆、类比这道题目：Find Median from Data Stream
1、将数字平均分配到两个堆、并保证最小堆的堆顶值大于最大堆的堆顶值
2、当数字增加到滑动窗口的大小的时候，计算median存入数组、并将最左边的值移出窗口、即从堆中移出。
时间复杂度：O（nk）
用treeset可以达到O（nlogk）、这里不介绍了，难度比较大，有兴趣的可以自行查看discuss
