我的算法书 - 单调队列

一句话算法

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

问题模型

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

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

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

[i-k+1,i]

中的最小值和最大值。

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

核心直觉

以求窗口最小值为例。

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

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

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

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

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

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

队列维护规则

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

求最小值时：

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

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

cpp

        1

        a[队尾] <= a[i]

算法步骤

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

算法证明

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

窗口合法

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

$q.front() \ge i-k+1$
单调性正确

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

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

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

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

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

复杂度分析

设序列长度为 $n$ 。

时间复杂度： $O(n)$ 。
空间复杂度： $O(k)$ ，队列中最多保存一个窗口内的候选元素；实现中通常开 $O(n)$ 数组或使用 deque。

代码实现

滑动窗口最小值和最大值：

C++

cpp

        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;
}

Python

C++ 版逻辑写在 main 里，Python 版抽成自由函数；a 为 1 下标（a[0] 占位），见文件头调用示例。

python

        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

        # 单调队列求滑动窗口最值：输出每个长度为 k 的窗口的最小值与最大值。
# a 为 1 下标（a[0] 占位不用），窗口数 n-k+1，要求 1 <= k <= n。
# 队列存下标且对应值单调：求最小用递增队列（队首最小），求最大用递减队列（队首最大）。
# 用 collections.deque 而非 list，保证队首删除是 O(1)。
# 调用示例：sliding_window_min_max([0, 3, 1, 4], 2) -> ([1, 1, 1], [3, 4, 4])

from collections import deque

type Arr = list[int]  # 1 下标数组，a[0] 占位不用


def sliding_window_min_max(a: Arr, k: int) -> tuple[Arr, Arr]:
    """返回 (每个窗口的最小值, 每个窗口的最大值)，两个列表长度都是 n-k+1。"""
    n = len(a) - 1
    mins: Arr = []
    maxs: Arr = []

    q: deque[int] = deque()
    for i in range(1, n + 1):
        # 队首下标滑出窗口 [i-k+1, i] 就弹出。
        while q and q[0] <= i - k:
            q.popleft()
        # 队尾对应值 >= a[i] 的永远不可能成为后面窗口的最小值，弹出。
        while q and a[q[-1]] >= a[i]:
            q.pop()
        q.append(i)
        if i >= k:
            mins.append(a[q[0]])

    q.clear()
    for i in range(1, n + 1):
        while q and q[0] <= i - k:
            q.popleft()
        # 求最大值时反向：队尾对应值 <= a[i] 的弹出。
        while q and a[q[-1]] <= a[i]:
            q.pop()
        q.append(i)
        if i >= k:
            maxs.append(a[q[0]])

    return mins, maxs

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

C++

cpp

        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;
}

Python

C++ 版逻辑写在 main 里，Python 版抽成自由函数；a 为 1 下标（a[0] 占位），见文件头调用示例。

python

        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

        # 单调队列 + 前缀和：求长度不超过 m 的最大子段和。
# a 为 1 下标（a[0] 占位不用），要求 n >= 1 且 m >= 1；此时答案一定存在（至少取一个元素）。
# prefix[i] = a[1] + ... + a[i]，子段 (j, i] 的和 = prefix[i] - prefix[j]。
# 固定右端 i 时，只需在 j ∈ [i-m, i-1] 里找最小的 prefix[j]，故用递增单调队列维护该窗口最小值。
# C++ 用 long long 防前缀和溢出 int；Python int 任意精度，该坑不存在。

from collections import deque

type Arr = list[int]  # 1 下标数组，a[0] / prefix[0] 占位不用


def max_subarray_sum(a: Arr, m: int) -> int:
    """返回长度 <= m 的非空子段最大和。调用示例：max_subarray_sum([0, 2, -1, 3], 2) -> 3"""
    n = len(a) - 1

    # prefix 同样 1 下标；prefix[0] = 0 作为空前缀哨兵。
    prefix: Arr = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = prefix[i - 1] + a[i]

    # n >= 1 时子段 (0, 1] 一定合法（m >= 1），用它当初始答案，
    # 避免像 C++ 那样用 LLONG_MIN 哨兵（Python 无固定下界）。
    answer = prefix[1] - prefix[0]
    q: deque[int] = deque([0])

    for i in range(1, n + 1):
        # 合法左端点 j 需满足 i - j <= m，即 j >= i - m。
        while q and q[0] < i - m:
            q.popleft()

        best = prefix[i] - prefix[q[0]]
        if best > answer:
            answer = best

        # 队尾 prefix 不小于 prefix[i] 的，作为左端点不如 i 优，弹出。
        while q and prefix[q[-1]] >= prefix[i]:
            q.pop()
        q.append(i)

    return answer

测试用例

滑动窗口输入：

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

输出：

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

应用分类详解

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

一、滑动窗口最值

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

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

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

应用场景	经典题目	核心思路
滑动窗口模板	luogu-P1886	分别维护递增队列和递减队列
固定窗口极值统计	LeetCode 239	队头始终是窗口最大值

二、前缀和窗口最值

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

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

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

\max(S_i-S_j)

其中：

j \in [i-m,i-1]

应用场景	经典题目	核心思路
最大子序和	AcWing 135	维护可选左端点的最小前缀和
长度受限最大区间和	常见前缀和题	右端点固定，左端点窗口滑动

三、DP 转移优化

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

识别信号： 转移中出现：

dp[i] = value(i) + \max_{j \in [L_i,R_i]} g(j)

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

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

应用场景	经典题目	核心思路
多重背包单调队列优化	背包进阶专题	同余类内维护窗口最大值
长度限制 DP	常见线性 DP	决策范围右移时维护最优前驱

经典例题

1. luogu-P1886

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

2. AcWing 135

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

3. LeetCode 239

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

参考

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