点击 这里 可以查看更多算法面试相关内容~

题目描述

中位数是有序序列最中间的那个数。

如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。

例如：

• [2,3,4]，中位数是 3
• [2,3]，中位数是 (2 + 3) / 2 = 2.5

给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。

窗口中有 k 个数，每次窗口向右移动 1 位。

你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

 示例：

给出 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
复制代码

 提示：

• 你可以假设 k 始终有效，即：k 始终小于输入的非空数组的元素个数。
• 与真实值误差在 10−510 ^ {-5}10−5 以内的答案将被视作正确答案。

朴素解法

一个直观的做法是：对每个滑动窗口的数进行排序，获取排序好的数组中的第 k / 2 和 (k - 1) / 2 个数（避免奇偶数讨论），计算中位数。

我们大概分析就知道这个做法至少 O(n∗k)O(n * k)O(n∗k) 的，算上排序的话应该是 O(n∗(k+klog⁡k))O(n * (k + k\log{k}))O(n∗(k+klogk))。

比较无奈的是，这道题不太正规，没有给出数据范围。我们无法根据判断这样的做法会不会超时。

PS. 实际上这道题朴素解法是可以过的，有蓝桥杯内味了 ~

朴素做法通常是优化的开始，所以我还是提供一下朴素做法的代码：

class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int cnt = n - k + 1;
        double[] ans = new double[cnt];
        int[] tmp = new int[k];
        for (int l = 0, r = l + k - 1; r < n; l++, r++) {
            for (int i = l; i <= r; i++) tmp[i - l] = nums[i];
            Arrays.sort(tmp);
            ans[l] = (tmp[k / 2] / 2.0) + (tmp[(k - 1) / 2] / 2.0);
        }
        return ans;
    }
}
复制代码

• 时间复杂度：最多有 n 个窗口需要滑动计算。每个窗口，需要先插入数据，复杂度为 O(k)O(k)O(k)，插入后需要排序，复杂度为 O(klog⁡k)O(k\log{k})O(klogk)。整体复杂度为 O(n∗(k+klog⁡k))O(n * (k + k\log{k}))O(n∗(k+klogk))。
• 空间复杂度：使用了长度为 k 的临时数组。复杂度为 O(k)O(k)O(k)。

优先队列（堆）解法

从朴素解法中我们可以发现，其实我们需要的就是滑动窗口中的第 k / 2 小的值和第 (k - 1) / 2 小的值。

我们知道滑动窗口求最值的问题，可以使用优先队列来做。

但这里我们求的是第 k 小的数，而且是需要两个值。还能不能使用优先队列来做呢？

我们可以维护两个堆：

• 一个大根堆维护着滑动窗口中一半较小的值（此时堆顶元素为滑动窗口中的第 (k - 1) / 2 小的值）
• 一个小根堆维护着滑动窗口中一半较大的值（此时堆顶元素为滑动窗口中的第 k / 2 小的值）

滑动窗口的中位数就是两个堆的堆顶元素的平均值。

实现细节：

1. 初始化时，先让 k 个元素直接入 right，再从 right 中倒出 k / 2 个到 left 中。这时候可以根据 left 和 right 得到第一个滑动窗口的中位值。
   
2. 开始滑动窗口，每次滑动都有一个待添加和待移除的数：
   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 多一个
        // 1.滑动窗口的左半部分
        PriorityQueue<Integer> left  = new PriorityQueue<>((a,b)->Integer.compare(b,a)); 
        // 2.滑动窗口的右半部分
        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(log⁡k)O(\log{k})O(logk)；窗口数量最多为 n。整体复杂度为 O(n∗log⁡k)O(n * \log{k})O(n∗logk)。
• 空间复杂度：最多有 n 个元素在堆内。复杂度为 O(n)O(n)O(n)。

注意点

今天的题解发到 LeetCode 后，针对一些同学的评论。

我觉得有一定的代表性，所以拿出来讲讲 ~

• (问)某同学：为什么 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 时，到导致溢出，返回的是 负数 ，而不是逻辑期望的 正数
  

同样具有溢出问题的还有计算第 k / 2 小的数和第 (k - 1) / 2 小的数的平均值时。

我是使用 (a / 2.0) + (b / 2.0) 的形式，而不是采用 (a + b) / 2.0 的形式。后者有相加溢出的风险。

最后

这是我们「刷穿 LeetCode」系列文章的第 No.* 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

由于 LeetCode 的题目随着周赛 & 双周赛不断增加，为了方便我们统计进度，我们将按照系列起始时的总题数作为分母，完成的题目作为分子，进行进度计算。当前进度为 */1916 。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：Github 地址 & Gitee 地址。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。