题目描述
这是 LeetCode 上的 480. 滑动窗口中位数 ，难度为 困难。
Tag : 「滑动窗口」、「堆」、「优先队列」
中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。
例如：
- [2,3,4][2,3,4]，中位数是 33
- [2,3][2,3]，中位数是 (2 + 3) / 2 = 2.5(2+3)/2=2.5
给你一个数组 numsnums，有一个长度为 kk 的窗口从最左端滑动到最右端。
窗口中有 kk 个数，每次窗口向右移动 11 位。
你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。
示例：
给出 nums = [1,3,-1,-3,5,3,6,7]，以及 k = 3。 窗口位置 中位数 --------------- ----- [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 因此，返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]。 复制代码
提示：
- 你可以假设 kk 始终有效，即：kk 始终小于等于输入的非空数组的元素个数。
- 与真实值误差在 10 ^ {-5}10−5 以内的答案将被视作正确答案。
朴素解法
一个直观的做法是：对每个滑动窗口的数进行排序，获取排序好的数组中的第 \frac{k}{2}2k 和 \frac{k - 1}{2}2k−1 个数（避免奇偶数讨论），计算中位数。
我们大概分析就知道这个做法至少 O(n * k)O(n∗k) 的，算上排序的话应该是 O(n * (k + k\log{k}))O(n∗(k+klogk))。
比较无奈的是，这道题的中文说明中没有给出数据范围。我们无法根据判断这样的做法会不会超时。
朴素做法通常是优化的开始，所以还是提供一下朴素做法的代码。
代码：
class Solution { public double[] medianSlidingWindow(int[] nums, int k) { int n = nums.length; int cnt = n - k + 1; double[] ans = new double[cnt]; int[] t = new int[k]; for (int l = 0, r = l + k - 1; r < n; l++, r++) { for (int i = l; i <= r; i++) t[i - l] = nums[i]; Arrays.sort(t); ans[l] = (t[k / 2] / 2.0) + (t[(k - 1) / 2] / 2.0); } return ans; } } 复制代码
- 时间复杂度：最多有
n个窗口需要滑动计算。每个窗口，需要先插入数据，复杂度为 O(k)O(k)，插入后需要排序，复杂度为 O(k\log{k})O(klogk)。整体复杂度为 O(n * (k + k\log{k}))O(n∗(k+klogk)) - 空间复杂度：使用了长度为
k的临时数组。复杂度为 O(k)O(k)
优先队列（堆）
从朴素解法中我们可以发现，其实我们需要的就是滑动窗口中的第 \frac{k}{2}2k 小的值和第 \frac{k - 1}{2}2k−1 小的值。
我们知道滑动窗口求最值的问题，可以使用优先队列来做。
但这里我们求的是第 kk 小的数，而且是需要两个值。还能不能使用优先队列来做呢？
我们可以维护两个堆：
- 一个大根堆维护着滑动窗口中一半较小的值（此时堆顶元素为滑动窗口中的第 \frac{k - 1}{2}2k−1 小的值）
- 一个小根堆维护着滑动窗口中一半较大的值（此时堆顶元素为滑动窗口中的第 \frac{k}{2}2k 小的值）
滑动窗口的中位数就是两个堆的堆顶元素的平均值。
实现细节：
- 初始化时，先让
k个元素直接入right，再从right中倒出 \frac{k}{2}2k 个到left中。这时候可以根据left和right得到第一个滑动窗口的中位值。 - 开始滑动窗口，每次滑动都有一个待添加和待移除的数：
2.1 根据与右堆的堆顶元素比较，决定是插入哪个堆和从哪个堆移除
2.2 之后调整两堆的大小（确保只会出现left.size() == right.size()或right.size() - left.size() == 1，对应了窗口长度为偶数或者奇数的情况）
2.3 根据left堆 和right堆得到当前滑动窗口的中位值
代码：
class Solution { public double[] medianSlidingWindow(int[] nums, int k) { int n = nums.length; int cnt = n - k + 1; double[] ans = new double[cnt]; // 如果是奇数滑动窗口，让 right 的数量比 left 多一个 PriorityQueue<Integer> left = new PriorityQueue<>((a,b)->Integer.compare(b,a)); // 滑动窗口的左半部分 PriorityQueue<Integer> right = new PriorityQueue<>((a,b)->Integer.compare(a,b)); // 滑动窗口的右半部分 for (int i = 0; i < k; i++) right.add(nums[i]); for (int i = 0; i < k / 2; i++) left.add(right.poll()); ans[0] = getMid(left, right); for (int i = k; i < n; i++) { // 人为确保了 right 会比 left 多，因此，删除和添加都与 right 比较（left 可能为空） int add = nums[i], del = nums[i - k]; if (add >= right.peek()) { right.add(add); } else { left.add(add); } if (del >= right.peek()) { right.remove(del); } else { left.remove(del); } adjust(left, right); ans[i - k + 1] = getMid(left, right); } return ans; } void adjust(PriorityQueue<Integer> left, PriorityQueue<Integer> right) { while (left.size() > right.size()) right.add(left.poll()); while (right.size() - left.size() > 1) left.add(right.poll()); } double getMid(PriorityQueue<Integer> left, PriorityQueue<Integer> right) { if (left.size() == right.size()) { return (left.peek() / 2.0) + (right.peek() / 2.0); } else { return right.peek() * 1.0; } } } 复制代码
- 时间复杂度：调整过程中堆大小最大为
k，堆操作中的指定元素删除复杂度为 O(k)O(k)；窗口数量最多为n。整体复杂度为 O(n * k)O(n∗k) - 空间复杂度：最多有
n个元素在堆内。复杂度为 O(n)O(n)
答疑
以下是针对一些具有代表性的问题进行的集中答疑：
- 为什么
new PriorityQueue<>((x,y)->(y-x))的写法会有某些案例无法通过？和new PriorityQueue<>((x,y)->Integer.compare(y,x))写法有何区别？(x,y)->(y-x)的写法逻辑没有错，AC 不了是因为 int 溢出。
在 Java 中 Integer.compare 的实现是(x < y) ? -1 : ((x == y) ? 0 : 1)。只是单纯的比较，不涉及运算，所以不存在溢出风险。
而直接使用y - x，当y = Integer.MAX_VALUE,x = Integer.MIN_VALUE时，到导致溢出，返回的是 负数 ，而不是逻辑期望的 正数
同样具有溢出问题的还有计算第 \frac{k}{2}2k 小的数和第 \frac{k - 1}{2}2k−1 小的数的平均值时。
因此题解中使用的是 (a / 2.0) + (b / 2.0) 的形式，而不是采用 (a + b) / 2.0 的形式。后者有相加溢出的风险。
复杂度说明
JDK 中 PriorityQueue 的 remove(Object o) 实现是先调用 indexOf(Object o) 方法进行线性扫描找到下标（复杂度为 O(n)O(n)），之后再调用 removeAt(int i) 进行删除（复杂度为 O(\log{n})O(logn)）。
对于本题而言，如果需要实现 O(\log{n})O(logn) 的 remove(Object o)， 只能通过引入其他数据结构（如哈希表）来实现快速查找元素在对堆数组中的下标。
对于本题，可以使用元素在原数组中的下标作为 key，在堆数组中的真实下标作为 val。
通过哈希表可以 O(1)O(1) 的复杂度找到下标，之后的删除只需要算堆调整的复杂度即可（最多 down 一遍，up 一遍，复杂度为 O(\log{n})O(logn)）。
至于 JDK 没有这样做的原因，猜测是因为基本类型的包装类型存在小数缓存机制，导致无法很好的使用哈希表来对应一个插入元素的下标。
举个🌰，我们调用三次 add(10)， 会有 33 个 1010 在堆内，但是由于小数（默认范围为 [-128,127][−128,127]）包装类型存在缓存机制，使用哈希表继续记录的话，只会有 { Integer.valueOf(10) : 移动过程中最后一次访问的数组下标 } 这样一条记录（add 进去的 1010 均为同一对象）。这时候删除一个 1010 之后，哈希表无法正确指导我们找到下一个 1010 的位置。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.480 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
