概念#

什么是单调队列#

单调队列是一种特殊的双端队列，其中的元素保持单调递增或单调递减的顺序。

特点：

· 双端操作：可以在队首和队尾进行插入和删除 · 单调性：队列中的元素始终保持单调递增或递减 · 时间复杂度：每个元素最多入队一次、出队一次，均摊O(1)

单调队列解决的问题#

主要应用：

滑动窗口最值问题 - 经典应用
优化动态规划 - 减少状态转移的时间复杂度
滑动窗口最值问题模板

问题描述：给定长度为n的序列a，窗口大小为k，窗口从左向右滑动，求每个窗口位置的最小值和最大值。

滑动窗口最值问题模板#

问题描述：给定长度为n的序列a，窗口大小k,窗口从左向右滑动，求每个窗口位置的最小值和最大值

求最小值（单调递增队列）#

1
// 维护单调递增队列
2
for i from 1 to n:
3
    while 队列非空且队尾元素 >= a[i]:
4
        弹出队尾
5
    将i加入队尾
6
    while 队首元素不在当前窗口内:
7
        弹出队首
8
    if i >= k:
9
        输出队首元素作为当前窗口最小值

求最大值（单调递减队列）#

1
// 维护单调递减队列
2
for i from 1 to n:
3
    while 队列非空且队尾元素 <= a[i]:
4
        弹出队尾
5
    将i加入队尾
6
    while 队首元素不在当前窗口内:
7
        弹出队首
8
    if i >= k:
9
        输出队首元素作为当前窗口最大值

完整代码实现#

1
#include <iostream>
2
#include <deque>
3
using namespace std;
4

5
const int N = 1e6 + 10;
6
int n, k;
7
int a[N];
8

9
int main() {
10
    cin >> n >> k;
11
    for (int i = 1; i <= n; i++) cin >> a[i];
12

13
    deque<int> q; // 存储下标
14

15
    // 窗口内最小值 - 单调递增队列
16
    for (int i = 1; i <= n; i++) {
17
        // 维护单调性：弹出所有大于等于当前元素的队尾元素
18
        while (q.size() && a[q.back()] >= a[i])
19
            q.pop_back();
20

21
        q.push_back(i);
22

23
        // 维护窗口大小：如果队首元素超出窗口范围，弹出
24
        if (i - q.front() + 1 > k)
25
            q.pop_front();
26

27
        // 输出结果：从第k个元素开始输出
28
        if (i >= k)
29
            cout << a[q.front()] << " ";
30
    }
31
    cout << endl;
32

33
    // 窗口内最大值 - 单调递减队列
34
    q.clear();
35
    for (int i = 1; i <= n; i++) {
36
        // 维护单调性：弹出所有小于等于当前元素的队尾元素
37
        while (q.size() && a[q.back()] <= a[i])
38
            q.pop_back();
39

40
        q.push_back(i);
41

42
        // 维护窗口大小
43
        if (i - q.front() + 1 > k)
44
            q.pop_front();
45

46
        // 输出结果
47
        if (i >= k)
48
            cout << a[q.front()] << " ";
49
    }
50
    cout << endl;
51

52
    return 0;
53
}

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

1
[1,3,-1.-3,5,3,6,7]
2
求最小值过程（单调递增队列）
3
窗口位置    队列状态(下标)    最小值
4
[1 3 -1]   [3]              -1
5
[3 -1 -3]  [4]              -3
6
[-1 -3 5]  [4]              -3
7
[-3 5 3]   [4,6]            -3
8
[5 3 6]    [6,7]            3
9
[3 6 7]    [7,8]            3
10

11
求最大值过程（单调递减队列）
12
窗口位置    队列状态(下标)    最大值
13
[1 3 -1]   [2]              3
14
[3 -1 -3]  [2]              3
15
[-1 -3 5]  [5]              5
16
[-3 5 3]   [5]              5
17
[5 3 6]    [7]              6
18
[3 6 7]    [8]              7

注意事项总结#

存储下标：队列中存储元素下标而不是值，便于判断元素是否在窗口内
维护单调性： · 最小值：弹出所有>=当前元素的队尾 · 最大值：弹出所有<=当前元素的队尾

维护窗口大小：

1
if (i - q.front() + 1 > k)
2
    q.pop_front();

输出时机：从第k个元素开始输出结果
时间复杂度：O(n)，每个元素最多入队出队一次

常见变种与应用#

多维度滑动窗口：处理二维或更高维度的滑动窗口
带权重的滑动窗口：元素带有权重的最值问题
动态规划优化：如多重背包问题的单调队列优化

掌握单调队列的核心在于理解其”淘汰机制”：永远保留对后续窗口计算最有潜力的元素，淘汰那些永远不会成为答案的元素。

音乐

音乐

概念#