引言：
LeetCode中遇到的一道题，记录一下。
转自 求滑动窗口中的中位数
问题定义
中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。（可以假设 k 始终有效，即：k 始终小于输入的非空数组的元素个数。）
双优先队列 + 延迟删除
思路与算法：
我们首先思考一下完成本题需要做哪些事情：
- 初始时，我们需要将数组 nums 中的前 k 个元素放入一个滑动窗口中，并且求出它们的中位数。
- 随着滑动窗口会向右进行移动。每一次移动后，会将一个新的元素放入滑动窗口中，并且将一个旧的元素移除滑动窗口，最后在求出它们的中位数。
因此，我们需要设计一个「数据结构」，用来维护滑动窗口，并且需要提供如下的三个接口：
- insert(num)：将一个数 num 加入该数据结构中
- erase(num)：将一个数 num 移除该数据结构
- getMedian()：返回当前数据结构中所有数的中位数
我们可以使用两个优先队列(堆)维护窗口内的所有元素，第一个优先队列 small 是一个大根对堆，它负责维护所有元素中较小的那一半；第二个优先队列 large 是一个小根堆，它负责维护所有元素中较大的那一半。具体地，如果当前需要维护的元素个数为 x，那么 samll 中维护了 ⌈x/2⌉ 个元素，large 中维护了 ⌊x/2⌋ 个元素，其中⌈y⌉和⌊y⌋分别表示将 y 向上取整和向下取整。也就是说：samll 中的元素个数要么与 large 中的元素个数相同，要么比 large 中的元素个数恰好多 1 个。这样设计的好处在于：当二者包含的元素个数相同时，它们各自的堆顶元素的平均值即为中位数；而当 small 包含的元素多了一个时，small 的堆顶元素即为中位数。这样 getMedian() 就设计完成了。
而对于 insert(num) 而言，如果当前两个优先队列都为空，那么根据元素个数的要求，我们必须将这个元素加入 small（显然不会存在 samll 空而 large 非空的情况）；如果 samll 非空，我们就可以将 num 与 samll 的堆顶元素top比较：
- 如果 num ≤ top，我们就将其加入 samll 中；
- 如果 num > top，我们就将其加入 large 中。
在成功地加入元素 num 之后，两个优先队列的元素个数可能会变得不符合要求。由于我们每次只是加入了一个元素，那么不符合要求的情况只能是下面二者之一：① small比large的元素个数多了2个；② small比large的元素个数少了1个。对于第一种情况，我们将 small 的堆顶元素放入 large 中；而对于第二种情况，我们将 large 的堆顶元素放入 samll 中。这样就可以解决问题了，insert(num)也就设计完成了。
然而对于 erase(num) 而言，设计起来就不是那么容易了，因为我们知道优先队列是不支持移除非堆顶元素这一操作的，因此我们可以考虑使用「延迟删除」这一技巧，即：
当我们需要移除优先队列中的某个元素时，我们只将这个删除操作「记录」下来，而不去真的删除这个元素。当这个元素出现在 small 或者 large 的堆顶时，我们再去将其移除对应的优先队列。
「延迟删除」使用到的辅助数据结构一般为哈希表 delayed，其中的每个键值对 <num, freq>表示元素 num 还需要被删除 freq 次。「优先队列 + 延迟删除」其实有非常多的设计方式，体现在「延迟删除」的时机选择上。在本解题中，我们使用一种比较容易编写代码的设计方式，即：
我们保证在任意操作 insert(num)，erase(num)，getMedian()完成之后（或者说任意操作开始之前），small 和 large 的堆顶元素都是不需要被「延迟删除」的。这样设计的好处在于：我们无需更改 getMedian()的设计，只需要略加修改 insert(num) 即可。
我们首先设计一个辅助函数 prune(heap)，它的作用很简单，就是对 heap 这个优先队列（small或者large之一），不断地弹出其需要被删除的堆顶元素，并且减少 delayed 中对应项的值。在 prune(heap) 完成之后，我们就可以保证 heap 的堆顶元素是不需要被「延迟删除」的。
这样我们就可以在 prune(heap) 的基础上设计出另一个辅助函数 makeBalance()，它的作用即为调整 small 和 large 中元素个数，使得二者元素满足要求。由于有了 erase(num) 以及「延迟删除」，我们在将一个优先队列的堆顶元素放入另一个优先队列后，第一个优先队列的堆顶元素可能变成为需要被删除的。因此我们就可以用 makeBalance() 将 prune(heap) 封装起来，它的逻辑如下：
- 如果 small 和 large 中的元素个数满足要求，则不进行任何操作；
- 如果 small 比 lareg 的元素个数多了 2 个，那么我们就将 small 的堆顶元素取出来放入 lareg 中。此时，small 的堆顶元素可能是需要被删除的，因此我们要调用 prune(small)；
- 如果 small 比 large 的元素个数少了 1 个，那么我们就将 large 的堆顶元素取出来放入 small 中。此时，large 的堆顶元素可能是需要被删除的，因此我们要调用 prune(large)。
此时，我们只需要在原先 insert(num) 的设计的最后加上一步 makeBalance()即可。然而对于 erase(num)，我们还需要进行进一步的思考：
- 如果 num 与 small 和 large 的堆顶元素都不相同，那么 num 是需要被「延迟删除」的，我们将其在哈希表中的值增加 1；
- 否则，例如 num 与 small 的堆顶元素相同，那么该元素是可以被立即删除的。虽然我们并没有实现「立即删除」这个辅助函数，但只要我们将 num 在哈希表中的值增加 1，并且调用「延迟删除」的辅助函数 prune(small)，那么就相当于实现了「立即删除」的功能。
无论是「立即删除」还是「延迟删除」，其中一个优先队列的元素个数发生了变化（减少了1），因此我们还需要用 makeBalance() 调整元素的个数。
此时，所有的接口都已经设计完了。由于 insert(num) 和 erase(num) 的最后一步都是 makeBalance()，而 makeBalance() 的最后一步是 prune(heap)，因此我们就保证了任意操作完成之后，small 和 large 的堆顶元素都是不需要被「延迟删除」的。
参考代码（java版）
public class LeetCodeTest {
@Test
public void test() {
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
double[] ans = medianSlidingWindow(nums, k);
System.out.println(Arrays.toString(ans));
}
public double[] medianSlidingWindow(int[] nums, int k) {
DualHeap dh = new DualHeap(k);
for (int i = 0; i < k; ++i) {
dh.insert(nums[i]);
}
double[] ans = new double[nums.length - k + 1];
ans[0] = dh.getMedian();
for (int i = k; i < nums.length; ++i) {
dh.insert(nums[i]);
dh.erase(nums[i - k]);
ans[i - k + 1] = dh.getMedian();
}
return ans;
}
}
class DualHeap {
// 大根堆，维护窗口中较小的一半元素（堆顶元素为最大值）
private PriorityQueue<Integer> small;
// 小根堆，维护窗口中较大的一半元素（堆顶元素为最小值）
private PriorityQueue<Integer> large;
// 哈希表，记录「延迟删除」的元素：key为元素，value为需要删除的次数
private Map<Integer, Integer> delayed;
// 窗口大小
private int k;
// samll 和 large 当前包含的有效元素个数，需要扣除被「延迟删除」的元素
private int smallSize, largeSize;
public DualHeap(int k) {
// 初始化 大根堆
this.small = new PriorityQueue<Integer>(new Comparator<Integer>(){
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
// 初始化 小根堆
this.large = new PriorityQueue<Integer>(Integer::compare);
this.delayed = new HashMap<Integer, Integer>();
this.k = k;
this.smallSize = 0;
this.largeSize = 0;
}
public double getMedian() {
return (k & 1) == 1 ? small.peek() : ((double) small.peek() + large.peek()) / 2;
}
public void insert(int num) {
if (small.isEmpty() || num <= small.peek()) {
small.offer(num);
++smallSize;
} else {
large.offer(num);
++largeSize;
}
makeBalance();
}
public void erase(int num) {
delayed.put(num, delayed.getOrDefault(num, 0) + 1);
if (num <= small.peek()) {
--smallSize;
if (num == small.peek()) {
prune(small);
}
} else {
--largeSize;
if (num == large.peek()) {
prune(large);
}
}
makeBalance();
}
// 不断地弹出 heap 的堆顶元素，并且更新哈希表
private void prune(PriorityQueue<Integer> heap) {
while (!heap.isEmpty()) {
int num = heap.peek();
if (delayed.containsKey(num)) {
delayed.put(num, delayed.get(num) - 1);
if (delayed.get(num) == 0) {
delayed.remove(num);
}
heap.poll();
} else {
break;
}
}
}
// 调整 small 和 large 中的元素个数，使得二者的元素个数满足要求
private void makeBalance() {
if (smallSize > largeSize + 1) {
//small 比 large 元素多 2 个
large.offer(small.poll());
--smallSize;
++largeSize;
prune(small);//small堆顶元素被移除，需要进行 prune，保证堆顶新元素已不再是需要被「延迟删除」的元素
} else if (smallSize < largeSize) {
//large 比 small 元素多 1 个
small.offer(large.poll());
--largeSize;
++smallSize;
prune(large);//large堆顶元素被移除，需要进行 prune，保证堆顶新元素已不再是需要被「延迟删除」的元素
}
}
}复杂度分析
由于「延迟删除」的存在，small 比 large 在最坏情况下可能包含所有的 n 个元素，即没有一个元素被真正删除了。因此优先队列的大小是 O(n) 而不是 O(k) 的，其中 n 是数组 nums 的长度。
- 时间复杂度：O(nlog(n))。insert(num) 和 erase(num) 的单次时间复杂度为 O(log(n))，getMedian() 的单次时间复杂度为 O(1)。因此总时间复杂度为 O(nlog(n))。
- 空间复杂度：O(n)。即为 small，large 和 delayed 需要使用的空间。
