Sliding Window

Java

public class Solution {
	
		public List<Integer> medianSlidingWindow(int[] nums, int k) {
		PriorityQueue<Integer> minHeap = new PriorityQueue<>();
		PriorityQueue<integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
		
		List<Integer> result = new ArrayList<>();
		for (int i = 0; i < nums.length; i++) {
			int num = nums[i];
			//new number
			maxHeap.offer(num);
			minHeap.offer(maxHeap.poll());           	//双堆求中位数的套路
				balance(minHeap, maxHeap);
		
				if (i >= k) {
					//remove
					if (nums[i - k] <= maxHeap.peek()) { 	//nums[i-k] 比大根堆的最大值还要小
						maxHeap.remove(nums[i - k]);  	//确认 nums[i-k] 是在maxHeap中
					} else {
						minHeap.remove(nums[i - k]);
					}
				}
				balance(minHeap, maxHeap);
				
				if (i >= k - 1) {   //这里为什么不是 i = k - 1 ?
					result.add(maxHeap.peek());
				}
		}
		
		private void balance(PriorityQueue<Integer> minHeap, PriorityQueue<Integer> maxHeap) {
			//0 <= len(maxHeap) - len(minHeap) <= 1; 1 或者是 0
			//奇偶都在maxHeap.peek(); 偶数的话需要返回左边的值，奇数返回中间的值
			while (maxHeap.size() < minHeap.size()) {
				maxHeap.offer(minHeap.poll());
			}
			while (maxHeap.size() - minHeap.size() > 1) {
				minHeap.offer(maxHeap.poll());
			}
		}
		}
}