Sign in Subscribe
算法

滑动窗口最大值

loser

• 7 min read
Share

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。

你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

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

示例 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

单调队列：

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> q;
        vector<int> ans;

        for (int i = 0; i < nums.size(); i++)
        {
            while (!q.empty() && q.front() <= i - k)
            {
                q.pop_front();
            }

            while (!q.empty() && nums[q.back()] <= nums[i])
            {
                q.pop_back();
            }

            q.push_back(i);

            if (i >= k - 1)
            {
                ans.push_back(nums[q.front()]);
            }
        }

        return ans;
    }
};

核心思想

这题最直接的想法是：每次窗口移动以后，都遍历窗口里的 k 个数，找出最大值。

这样每个窗口需要 O(k)，一共有大约 n 个窗口，总时间复杂度就是 O(nk)。

当 n 很大时，这个方法会超时。

我们需要一种结构，可以快速知道当前窗口最大值。

这就是单调队列。

单调队列中维护的是一组下标，并且这些下标对应的值从队头到队尾单调递减：

nums[q[0]] >= nums[q[1]] >= nums[q[2]] >= ...

这样一来，队头下标对应的值就是当前窗口中的最大值。

为什么队列里存下标

队列里不直接存值，而是存下标。

原因有两个：

1. 判断元素是否离开窗口

当遍历到下标 i 时，当前窗口范围是：

[i - k + 1, i]

如果队头下标：

q.front() <= i - k

说明这个下标已经在窗口左边，离开当前窗口了，需要弹出。

代码是：

while (!q.empty() && q.front() <= i - k)
{
    q.pop_front();
}

如果只存值，就无法知道这个值是不是已经过期。

2. 通过下标访问原数组值

虽然队列里存的是下标，但比较大小时可以直接用：

nums[q.back()]

和当前值：

nums[i]

进行比较。

这样既能判断是否过期，又能比较大小。

为什么要弹出队尾更小的元素

当遍历到新元素 nums[i] 时，如果队尾元素满足：

nums[q.back()] <= nums[i]

那么队尾元素就可以被删除。

原因是：

  1. 队尾元素比当前元素小或者相等。
  2. 当前元素下标更靠右，会比队尾元素更晚离开窗口。

所以只要当前元素还在窗口里，队尾元素就不可能再成为最大值。

既然它以后也没有机会成为答案，就可以直接弹掉。

代码是：

while (!q.empty() && nums[q.back()] <= nums[i])
{
    q.pop_back();
}

弹完以后，再把当前下标加入队尾：

q.push_back(i);

这样队列就能继续保持从队头到队尾单调递减。

队头为什么就是窗口最大值

队列维护了两个性质：

  1. 队列里的下标都在当前窗口内。
  2. 队列里的值从队头到队尾单调递减。

根据第 2 点，队头元素是队列中最大的。

根据第 1 点，队列中的元素都属于当前窗口。

同时，所有可能成为窗口最大值的元素都会被保留在队列中。

所以队头元素就是当前窗口最大值：

nums[q.front()]

当 i >= k - 1 时，说明第一个完整窗口已经形成，此后每一步都可以加入一个答案：

if (i >= k - 1)
{
    ans.push_back(nums[q.front()]);
}

正确性证明

我们证明：算法在每个窗口形成后加入答案的值，都是该窗口的最大值。

结论 1：队列中的下标始终在当前窗口内

每次处理下标 i 时，当前窗口左边界是：

i - k + 1

任何满足：

q.front() <= i - k

的下标都已经小于窗口左边界，说明它离开了窗口。

代码会在每一轮开始时把这些过期下标从队头删除。

因此，当加入答案时，队列中的下标都在当前窗口内。

结论 2：队列中的值始终单调递减

加入新下标 i 之前，代码会不断弹出队尾中小于等于 nums[i] 的元素：

while (!q.empty() && nums[q.back()] <= nums[i])
{
    q.pop_back();
}

弹出结束后，如果队列不为空，那么一定有：

nums[q.back()] > nums[i]

然后再把 i 加入队尾。

所以加入后，队列仍然保持从队头到队尾严格递减。

因此队头对应的值一定是队列中的最大值。

结论 3：被弹出的队尾元素不可能成为之后窗口的最大值

设某个队尾下标是 j，当前下标是 i，并且：

j < i

nums[j] <= nums[i]

由于 i 比 j 更靠右，所以在之后的滑动窗口中：

  • 如果 j 还在窗口里，那么 i 一定也还在窗口里
  • nums[i] 又不小于 nums[j]

所以 j 不可能比 i 更适合作为最大值。

因此弹出 j 不会影响任何之后窗口的答案。

结论 4：队头就是当前窗口最大值

根据结论 1，队列中的所有下标都在当前窗口内。

根据结论 2，队头是队列中的最大值。

根据结论 3，所有被删除的元素都不可能成为当前或未来窗口的最大值。

所以当前窗口的最大值一定是：

nums[q.front()]

算法每次窗口形成后都把这个值加入答案，因此答案正确。

举例理解

以：

nums = [1,3,-1,-3,5,3,6,7], k = 3

为例。

前几个位置的处理过程：

处理 1

队列为空，直接加入下标 0。

队列对应值：

[1]

处理 3

3 比队尾 1 大，所以 1 不可能再成为最大值，弹出 1。

加入 3。

队列对应值：

[3]

处理 -1

-1 比队尾 3 小，直接加入。

队列对应值：

[3, -1]

此时第一个窗口 [1, 3, -1] 形成，最大值是队头 3。

处理 -3

-3 比队尾 -1 小，直接加入。

队列对应值：

[3, -1, -3]

当前窗口 [3, -1, -3]，最大值仍然是队头 3。

处理 5

5 会把队尾所有比它小的元素都弹掉：

  • -3 被弹出
  • -1 被弹出
  • 3 被弹出

然后加入 5。

队列对应值：

[5]

当前窗口 [-1, -3, 5]，最大值是 5。

复杂度分析

每个下标最多入队一次，也最多出队一次。

所以所有队列操作总次数是 O(n)。

因此总时间复杂度是：

O(n)

队列中最多存放 k 个下标，所以空间复杂度是：

`O(k)