📝 题目描述

题目链接：滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 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       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 1 <= k <= nums.length

💡 解题思路

方法一：优先队列

对于保持一段数据的最大值，很容易想到的一个数据结构就是“堆”，也就是C++里面的优先队列，默认的大顶堆可以帮助我们实时维护一系列元素中的最大值。

具体而言，我们的流程可以按下面的描述进行：

  • 首先，在保证堆不空的情况下，检查堆顶元素（也就是最大值）是否过期（也就是是否还在长度为 k 的窗口内），是则不断弹出堆顶元素，直到不过期；
  • 将当前元素加入堆中；
  • 若窗口填充满，则查看堆顶元素，记录到答案数组中。

上面的流程有一些细节要注意。
首先堆中存储的数据结构，因为堆的维护需要进行元素的大小比较，而判断过期又要需要用到元素的索引，所以为了方便，我们可以存储一个 pair 到堆中，具体是 (nums[i], i) ，这样就可以满足我们的需求。

方法二：单调队列

我们可以顺着方法一的思路继续进行优化。

由于我们需要求出的是滑动窗口的最大值，如果当前的滑动窗口中有两个下标 i 和 j，其中 i 在 j 的左侧（i < j），并且 i 对应的元素不大于 j 对应的元素（nums[i] ≤ nums[j]），那么会发生什么呢？

当滑动窗口向右移动时，只要 i 还在窗口中，那么 j 一定也还在窗口中，这是 i 在 j 的左侧所保证的。同时，由于 nums[j] 的存在，nums[i] 一定不会是滑动窗口中的最大值了，我们可以将 nums[i] 永久地移除。

因此我们可以使用一个队列存储所有还没有被移除的下标。在队列中，这些下标按照从小到大的顺序被存储，并且它们在数组 nums 中对应的值是严格单调递减的。

按照上面的想法，我们的流程可以按下面的描述进行：

  • 首先，在保证队列不空的情况下，检查队首的元素（也就是最大值）是否过期（也就是是否还在长度为 k 的窗口内），是则不断移除队列队首元素，直到不过期；
  • 在保证队列不空的情况下，将当前元素不断与队尾元素比较，因为我们要求队列严格递减，因此如果队尾元素小于等于当前元素，则将其移除；
  • 将当前元素加入队尾中；
  • 若窗口填充满，则查看队首元素，记录到答案数组中。

方法三：分块 + 预处理

这是一个另类的解法，假设 nums 数组中有 n 个元素，我们按照 k 个一组的方式，从左往右进行分组（最后一组中元素的数量可能会不足 k 个）。此时如果我们希望求出 nums[i] 到 nums[i + k − 1] 的最大值，就会有两种情况：

  • 如果 i 是 k 的倍数，那么 nums[i] 到 nums[i + k − 1] 恰好是一个分组。我们只要预处理出每个分组中的最大值，即可得到答案；
  • 如果 i 不是 k 的倍数，那么 nums[i] 到 nums[i + k − 1] 会跨越两个分组，占有第一个分组的后缀以及第二个分组的前缀。假设 j 是 k 的倍数，并且满足 i < j ≤ i + k − 1，那么 nums[i] 到 nums[j−1] 就是第一个分组的后缀，nums[j] 到 nums[i + k − 1] 就是第二个分组的前缀。如果我们能够预处理出每个分组中的前缀最大值以及后缀最大值，同样可以在 O(1)O(1) 的时间得到答案。

以上面的图片为例：
假设n = 15, k = 4, i = 6，我们寻找 nums[6] 到 nums[6 + 4 - 1 = 9] 区间的最大值，那么此时跨越了两个分组，因此我们需要找出 6 < j ≤ 9 同时 j 也要是 k 的倍数，即 j = 8。
此时nums[6] 到 nums[7]就是第一个分组的后缀，nums[8] 到 nums[9] 就是第二个分组的前缀。

那么如何预先处理好每个分组中的前缀最大值以及后缀最大值呢？对于每个元素 nums[i] ：

限定在本组中，以 nums[i] 结尾的前缀最大值prefixMax的处理如下：

prefixMax[i]={nums[i], i 是 k 的倍数 max{nums[i],prefixMax[i−1]}, i 不是 k 的倍数 prefixMax[i] = \begin{cases} nums[i], & \text{ i 是 k 的倍数 } \\ max\{nums[i], prefixMax[i - 1]\}, & \text{ i 不是 k 的倍数 } \end{cases}

限定在本组中，以 nums[i] 开头的后缀最大值suffixMax的处理如下：

suffixMax[i]={nums[i], i + 1 是 k 的倍数 max{nums[i],suffixMax[i+1]}, i + 1 不是 k 的倍数 suffixMax[i] = \begin{cases} nums[i], & \text{ i + 1 是 k 的倍数 } \\ max\{nums[i], suffixMax[i + 1]\}, & \text{ i + 1 不是 k 的倍数 } \end{cases}

需要注意在递推 suffixMax[i] 时需要考虑到边界条件 suffixMax[n − 1] = nums[n − 1]，而在递推 prefixMax[i] 时的边界条件 prefixMax[0] = nums[0] 恰好包含在递推式的第一种情况中，因此无需特殊考虑。

在预处理完成之后，对于 nums[i] 到 nums[i + k − 1] 的所有元素，如果 i 不是 k 的倍数，那么窗口中的最大值为 suffixMax[i] 与 prefixMax[i + k − 1] 中的较大值；如果 i 是 k 的倍数，那么此时窗口恰好对应一整个分组，suffixMax[i] 和 prefixMax[i + k − 1] 都等于分组中的最大值，因此无论窗口属于哪一种情况，

maxsuffixMax[i],prefixMax[i+k−1]max{suffixMax[i],prefixMax[i+k−1]}

即为答案

🔧 代码实现

1、优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> pri_que;
        int n = nums.size(), i = 0;
        vector<int> ans;
        while(i < n){
            // 移除过期元素
            while((!pri_que.empty()) && (pri_que.top().second <= i - k)){
                pri_que.pop();
            }
            // 加入当前元素
            pri_que.push({nums[i], i});

            if (i >= k - 1) ans.push_back(pri_que.top().first);
            i++;
        }
        return ans;
    }
};

2、单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> ans;
        deque<int> dq;
        for(int i = 0; i < n; i++){
            // 移除过期元素
            if(!(dq.empty()) && (dq.front() <= i - k)){
                dq.pop_front();
            }
            // 移出比当前元素小的元素
            while(!(dq.empty()) && (nums[dq.back()] <= nums[i])){
                dq.pop_back();
            }
            // 加入当前元素
            dq.push_back(i);

            // 将最大数字插入答案
            if(i >= k - 1) ans.push_back(nums[dq.front()]);
        }
        return ans;
    }
};

3、分块 + 预处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> prefixMax(n), suffixMax(n), ans;
        for(int i = 0; i < n; i++){
            if(i % k == 0){
                prefixMax[i] = nums[i];
            } else {
                prefixMax[i] = max(prefixMax[i - 1], nums[i]);
            }
        }
        for(int i = n - 1; i >= 0; i--){
            if((i == n - 1) || ((i + 1) % k == 0)){
                suffixMax[i] = nums[i];
            } else {
                suffixMax[i] = max(suffixMax[i + 1], nums[i]);
            }
        }
        for(int i = 0; i <= n - k; i++){
            ans.push_back(max(suffixMax[i], prefixMax[i + k - 1]));
        }
        return ans;
    }
};

📊 复杂度分析

1、优先队列

  • 时间复杂度：O(nlogn)O(nlogn)，其中 n 是数组 nums 的长度。在最坏情况下，数组 nums 中的元素单调递增，那么最终优先队列中包含了所有元素，没有元素被移除。由于将一个元素放入优先队列的时间复杂度为 O(logn)，因此总时间复杂度为 O(nlogn)。
  • 空间复杂度：O(n)O(n)，即为优先队列需要使用的空间。这里所有的空间复杂度分析都不考虑返回的答案需要的 O(n) 空间，只计算额外的空间使用。

2、单调队列

  • 时间复杂度：O(n)O(n)，其中 n 是数组 nums 的长度。每一个下标恰好被放入队列一次，并且最多被弹出队列一次，因此时间复杂度为 O(n)。
  • 空间复杂度：O(k)O(k)。与方法一不同的是，在方法二中我们使用的数据结构是双向的，因此“不断从队首弹出元素”保证了队列中最多不会有超过 k+1 个元素，因此队列使用的空间为 O(k)。

3、分块 + 预处理

  • 时间复杂度：O(n)O(n)，其中 n 是数组 nums 的长度。我们需要 O(n) 的时间预处理出数组 prefixMax，suffixMax 以及计算答案。
  • 空间复杂度：O(n)O(n)，即为存储 prefixMax 和 suffixMax 需要的空间。

🎯 总结

  • 核心思想：要熟练掌握标准解法（前两种），想起来使用优先队列/双端队列。