题目描述

题目链接

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

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

示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：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：

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

算法1

(单调队列) $O(n)$

题目要求我们维护一个滑动窗口，窗口每次移动一个位置
输出每个窗口内的最大值
那么这是一个经典的滑动窗口 + 单调队列的算法
如果考虑使用暴力方法，即对每一个窗口都遍历其内部元素，那么很容易发现是 $O(n^2)$的算法
因此，我们需要考虑进行优化

我们可以发现，在一个窗口中，在最大值之后的所有元素都是无效的，因为只要最大值仍然在窗口内部，那么比最大值小的值无论如何都不可能称为最大值。
因此，根据这个单调特性，我们可以构建一个单调队列，在这个队列中，我们存放每个窗口的最大值的下标

每次遍历到一个位置时，尝试将其加入队列中
如果当前的队尾元素小于将要加入的元素，那么说明新加入的元素永远比当前队尾元素晚移出窗口，并且大于当前队尾元素，那么无论如何队尾元素都不可能成为最大值，因此可以直接将其删除，迭代进行这个操作，直到队尾元素大于当前要加入的值或队列为空

那么，这样一个队列一定是单调递减的，因此称为单调队列

每次输入队头，即可得到每个窗口内的最大值

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) {
        int n = nums.size();
        vector<int> res;
        vector<int> q (n);
        int hh = 0, tt = -1;

        for(int i = 0; i < n; i ++)
        {
            if( q[hh] < i - k + 1) hh ++;
            while( hh <= tt && nums[q[tt]] <= nums[i]) tt --;
            q[++ tt] = i;

            if( i - k + 1 >= 0) res.push_back(nums[q[hh]]);
        }

        return res;
    }
};