单调队列

一句话算法

单调队列只保留窗口里还有机会成为答案的元素：过期的从队头删，更差的从队尾删。

问题模型

单调队列常用来解决这类问题：

给定一个序列，窗口从左到右移动，每次需要快速得到窗口中的最小值或最大值。

例如窗口长度为 $k$，要求每个区间：

中的最小值和最大值。

暴力做法每个窗口扫描 $k$ 个元素，总复杂度是 $O(nk)$。单调队列把每个元素最多进队一次、出队一次，总复杂度降到 $O(n)$。

核心直觉

以求窗口最小值为例。

如果新来的数 x 比队尾元素更小，那么队尾元素以后不可能再成为最小值：

• 队尾元素更早进入窗口，会更早过期；
• 队尾元素的值还更大；
• 所以它被 x 完全淘汰。

因此队列中只保留“下标递增、值也递增”的候选元素。

队头                         队尾
下标:  increasing increasing increasing
数值:  small      ...        large

队头就是当前窗口的最小值。

求最大值时方向反过来：队列中维护值递减，队头是最大值。

队列维护规则

每次处理位置 i 时，队列中存的是下标。

求最小值时：

1. 删除队头中过期的下标。
2. 删除队尾中所有 a[队尾] >= a[i] 的下标。
3. 把 i 加入队尾。
4. 当窗口长度已经达到 k 时，a[队头] 就是当前窗口最小值。

求最大值时，把第二步改成：

        
1

        a[队尾] <= a[i]
    

算法步骤

1. 初始化一个双端队列 q。
2. 从左到右枚举每个位置 i。
3. 先弹出所有已经不在窗口 [i-k+1,i] 中的队头下标。
4. 再从队尾弹出所有不如当前元素的候选。
5. 把当前下标 i 入队。
6. 如果 i >= k，队头就是当前窗口答案。

算法证明

核心不变量：处理完位置 $i$ 后，队列中保存的下标都在当前窗口内，并且对应值保持单调；所有被删除的元素都不可能成为当前或未来窗口答案。

1. 窗口合法

   每次先删除过期下标。删除后，队列中所有下标都满足：

   $$q.front() \ge i-k+1$$

2. 单调性正确

   求最小值时，如果队尾元素 $a_j \ge a_i$，且 $j<i$，那么 $a_j$ 比 $a_i$ 更大或相等，还会更早离开窗口。

   因此 $a_j$ 永远不会比 $a_i$ 更适合作为最小值，可以删除。

3. 队头最优

   删除完过期元素和劣质元素后，队列按值递增。队头是队列中值最小的元素，也就是当前窗口最小值。

4. 复杂度线性

   每个下标只会入队一次，最多从队头或队尾出队一次，所以总操作次数是线性的。

因此单调队列维护窗口最值正确。

复杂度分析

设序列长度为 $n$。

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(k)$，队列中最多保存一个窗口内的候选元素；实现中通常开 $O(n)$ 数组或使用 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;
}
    

长度不超过 $m$ 的最大子段和：

        
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

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

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

    vector<long long> prefix(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        prefix[i] = prefix[i - 1] + x;
    }

    long long ans = LLONG_MIN;
    deque<int> q;
    q.push_back(0);

    for (int i = 1; i <= n; i++) {
        while (!q.empty() && q.front() < i - m) {
            q.pop_front();
        }

        ans = max(ans, prefix[i] - prefix[q.front()]);

        while (!q.empty() && prefix[q.back()] >= prefix[i]) {
            q.pop_back();
        }
        q.push_back(i);
    }

    cout << ans << "\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

最大子序和输入：

6 3
1 -2 3 5 -1 2

输出：

8

解释：长度不超过 3 的最大子段是 3 5，和为 8。

应用分类详解

单调队列的本质是：在一个不断右移的候选区间里，维护最优候选。它适合“候选集合像滑动窗口一样进一出一，并且比较标准是最大值或最小值”的问题。

一、滑动窗口最值

典型模式： 固定长度窗口移动，查询每个窗口的最大值或最小值。

识别信号： 出现“连续 $k$ 个元素”“每个窗口”“区间最大/最小”。

核心建模： 队列存下标，队头是当前窗口最优值。

二、前缀和窗口最值

典型模式： 区间和写成两个前缀和相减，其中一个端点在长度限制内滑动。

识别信号： 出现“长度不超过 $m$ 的最大子段和”“区间长度有限制”“最大连续和但不能太长”。

核心建模： 对每个右端点 $i$，需要找窗口内最小的前缀和：

其中：

三、DP 转移优化

典型模式： 状态转移形如“从一段连续前驱状态中取最大值或最小值”。

识别信号： 转移中出现：

且 $[L_i,R_i]$ 随 $i$ 单调右移。

核心建模： 把可选前驱 $j$ 放进单调队列，队头就是当前最优决策。

经典例题

1. luogu-P1886

滑动窗口模板题。重点是分别维护最小值队列和最大值队列。

2. AcWing 135

最大子序和。把区间和转成前缀和差，问题变成维护一个滑动窗口内的最小前缀和。

3. LeetCode 239

滑动窗口最大值。只需要维护递减队列，是单调队列的标准应用。

参考

• 本文旧版解析保留的核心思路：排除不可能成为答案的候选，动态维护滑动区间的最优候选队列。