滑动窗口最值

一句话算法

滑动窗口最值用单调队列维护候选下标，队头就是当前窗口答案。

问题模型

给定长度为 $n$ 的序列和窗口长度 $k$，窗口从左到右滑动，输出每个窗口的最小值和最大值。

这是单调队列最直接的模板题。完整讲解见单调队列。

核心直觉

求最小值时，如果新元素比队尾元素更小，那么队尾元素更早过期、值还更大，以后不可能成为最小值，可以从队尾删除。

求最大值时同理，只是比较方向相反。

算法步骤

以维护窗口最小值为例：

1. 用双端队列 q 保存候选下标。
2. 枚举当前位置 i。
3. 若队头下标已经离开窗口，即 q.front() <= i-k，从队头弹出。
4. 若队尾元素值 a[q.back()] >= a[i]，说明它比新元素更大且更早过期，从队尾弹出。
5. 将当前下标 i 加入队尾。
6. 当 i >= k 时，a[q.front()] 就是当前窗口最小值。

维护最大值时，第 4 步改为弹出所有 a[q.back()] <= a[i] 的下标。

算法证明

核心不变量： 队列中的下标都在当前窗口内，并且对应值按需要保持单调。

以最小值队列为例：

1. 窗口合法。 每次处理新位置前删除过期队头，所以队列中剩余下标都属于当前窗口。
2. 被删元素无用。 若 j<i 且 a[j] >= a[i]，那么 j 更早过期，值还不小于 i，以后不可能比 i 更适合作为最小值。
3. 队头最优。 队列按值递增，队头就是所有候选中值最小的下标。
4. 不漏答案。 只有过期元素和被新元素完全支配的元素会被删除，真正可能成为未来答案的候选都会保留。

所以队头始终给出当前窗口最小值。最大值同理，只需把比较方向反过来。

复杂度分析

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

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(k)$，实现中使用 deque 保存候选下标。

代码实现

        
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

        #include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    deque<int> q;
    for (int i = 1; i <= n; i++) {
        while (!q.empty() && q.front() <= i - k) {
            q.pop_front();
        }
        while (!q.empty() && a[q.back()] >= a[i]) {
            q.pop_back();
        }
        q.push_back(i);
        if (i >= k) {
            cout << a[q.front()] << (i == n ? '\n' : ' ');
        }
    }

    q.clear();
    for (int i = 1; i <= n; i++) {
        while (!q.empty() && q.front() <= i - k) {
            q.pop_front();
        }
        while (!q.empty() && a[q.back()] <= a[i]) {
            q.pop_back();
        }
        q.push_back(i);
        if (i >= k) {
            cout << a[q.front()] << (i == n ? '\n' : ' ');
        }
    }

    return 0;
}
    

测试用例

输入：

8 3
1 3 -1 -3 5 3 6 7

输出：

-1 -3 -3 -3 3 3
3 3 5 5 6 7

经典例题

1. luogu-P1886

标准滑动窗口最值。先输出所有窗口最小值，再输出所有窗口最大值。

2. LeetCode 239

只需要维护窗口最大值。写一个递减队列即可。

应用分类详解

滑动窗口最值的本质是：固定长度区间不断右移，快速维护区间最大值或最小值。

一、固定窗口极值

• 典型模式： 每个长度为 $k$ 的连续区间都要求最大值、最小值或极差。
• 识别信号： 出现“连续 $k$ 个元素”“每个窗口”“区间最大/最小”。
• 核心建模： 队列存下标，队头是当前窗口最优值。

二、区间约束中的最优候选

• 典型模式： 每一步只允许从最近 $k$ 个位置中选一个最优前驱。
• 识别信号： 转移或统计范围形如 [i-k+1,i]。
• 核心建模： 把候选下标放进单调队列，范围右移时删除过期下标。