480. Sliding Window Median

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 k numbers 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.

思路：最大堆 + 最小堆 无疑，那写吧

import java.util.Comparator; import java.util.PriorityQueue; /* * 最大堆 + 最小堆无疑，关键在于怎么更新数据 */ public class Solution { public double[] medianSlidingWindow(int[] nums, int k) { PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>(){ @Override public int compare(Integer o1, Integer o2) { return o2-o1; } }); for(int i=0; i<k; i++) { minHeap.add(nums[i]); if(minHeap.size() > maxHeap.size()) maxHeap.add(minHeap.remove()); } double[] ret = new double[nums.length-k+1]; if(k % 2 == 1) ret[0] = maxHeap.peek(); else ret[0] = (maxHeap.peek() + minHeap.peek()) / 2.0; for(int i=k; i<nums.length; i++) { if(nums[i-k] > maxHeap.peek()) minHeap.remove(nums[i-k]); else maxHeap.remove(nums[i-k]); if(maxHeap.size() - minHeap.size() > 1) minHeap.add(maxHeap.remove()); minHeap.add(nums[i]); if(minHeap.size() > maxHeap.size()) maxHeap.add(minHeap.remove()); if(k % 2 == 1) ret[i-k+1] = maxHeap.peek(); else ret[i-k+1] = (maxHeap.peek() + minHeap.peek()) / 2.0; } return ret; } } 发现加数据的过程中，可能会出现长度差失控和不满足minHeap的最小值比maxHeap的最大值大的现象，思考了之后，发现以下方案可以控制2个优先队列的差值最大为1：假设minHeap的长度可以比maxHeap的长度大1

先加到先加到maxHeap，再把maxHeap最大的加到minHeap，这样就能保证minHeap的最小值比maxHeap的最大值仍然要大

加完自后判断minHeap的长度与maxHeap的长度差值，如果大于1，把minHeap中拿出一个数据到maxHeap

写完发现一些corner case过不了，比如-2147483648,-2147483648，自然就是排序的时候不能直接减，会overflow，那就转成long吧

return (int) ((long)o2-(long)o1); 这样也有问题，cast to int的时候仍然会overflow

好吧，只能这样判断下了：

if(o2 > o1) return 1; else return -1; package l480; import java.util.Comparator; import java.util.PriorityQueue; public class Solution { public double[] medianSlidingWindow(int[] nums, int k) { PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(2*k, new Comparator<Integer>(){ @Override public int compare(Integer o1, Integer o2) { // 这里排序会有问题，即使是这样减完也不能cast to int // return (int) ((long)o2-(long)o1); if(o2 > o1) return 1; else return -1; } }); // 先加到少的，再加到大的 for(int i=0; i<k; i++) { // 这里设置的是minHeap的长度更长 maxHeap.add(nums[i]); // 为什么debug不能add？因为watch了pq.remove()，会自动运行一下的 minHeap.add(maxHeap.remove()); if(minHeap.size() - maxHeap.size() > 1) maxHeap.add(minHeap.remove()); } double[] ret = new double[nums.length-k+1]; if(k % 2 == 1) ret[0] = minHeap.peek(); else ret[0] = (0.0 + maxHeap.peek() + minHeap.peek()) / 2.0; for(int i=k; i<nums.length; i++) { if(maxHeap.isEmpty() || nums[i-k] > maxHeap.peek()) minHeap.remove(nums[i-k]); else maxHeap.remove(nums[i-k]); if(minHeap.size() - maxHeap.size() > 1) maxHeap.add(minHeap.remove()); else if(minHeap.size() < maxHeap.size()) minHeap.add(maxHeap.remove()); maxHeap.add(nums[i]); minHeap.add(maxHeap.remove()); if(minHeap.size() - maxHeap.size() > 1) maxHeap.add(minHeap.remove()); if(k % 2 == 1) ret[i-k+1] = minHeap.peek(); else ret[i-k+1] = (0.0 + maxHeap.peek() + minHeap.peek()) / 2.0; } return ret; } }

在这过程遇到一个蛋疼的问题是：在debug模式下有时候不能添加数据到优先队列中，但是直接run就可以，后来发现是watch了一个表达式：pq.remove()，每次断点停下来就会运行一下，自然就删除了数据

2刷，行数变少了

import java.util.Comparator; import java.util.PriorityQueue; class Solution { public double[] medianSlidingWindow(int[] nums, int k) { double[] ret = new double[nums.length - k + 1]; PriorityQueue<Integer> larger = new PriorityQueue<Integer>(); PriorityQueue<Integer> smaller = new PriorityQueue<Integer>(k, new Comparator<Integer>(){ public int compare(Integer o1, Integer o2) { if(o2 > o1) return 1; else return -1; } }); for(int i=0; i<nums.length; i++) { smaller.add(nums[i]); larger.add(smaller.remove()); if(larger.size() - smaller.size() > 1) smaller.add(larger.remove()); if(i >= k-1) { if(k % 2 == 1) ret[i-k+1] = larger.peek(); else ret[i-k+1] = (0.0 + larger.peek() + smaller.peek()) / 2.0; if(nums[i-k+1] >= larger.peek()) larger.remove(nums[i-k+1]); else smaller.remove(nums[i-k+1]); } } return ret; } }