← 目录 / 算法文档 · 模块六 单调栈与单调队列 / 6.2 单调队列

6.2　单调队列

窗口在数组上滑动，每移动一步都要知道窗口里的最大值——单调队列能做到全程 O(n)。

本页目录
① 为什么需要单调队列

有一类问题：一个固定大小为 k 的"窗口"，从数组最左边开始，每次往右滑动一格，每滑动一步都要知道当前窗口里的最大值。最直接的想法是每滑动一次，就把窗口里的 k 个数重新比一遍找最大值——数组长度是 n 时，总共要做大约 O(n×k) 次比较，如果 k 比较大，会很慢。

单调队列能把这个问题优化到 O(n)。它和 6.1 节的单调栈是近亲——同样是"维护单调性、提前清理不再有用的数据"，区别在于单调队列用的是双端队列（两端都能进出），需要同时处理"窗口滑出去"和"新数据更优"这两种淘汰情况。

② 用单调队列求滑动窗口最大值

用数组 {1, 3, -1, -3, 5, 3, 6, 7}、窗口大小 k=3 演示。维护一个双端队列，队列里存下标，对应的数值从队头到队尾保持递减。每来一个新数 arr[i]，要做两件事：

C++ · 单调队列求滑动窗口最大值
1vector<int> SlidingWindowMax(vector<int> arr, int k)
2{
3 int n = arr.size();
4 deque<int> dq; // 存下标，对应数值从队头到队尾递减
5 vector<int> result;
6
7 for (int i = 0; i < n; i++)
8 {
9 if (!dq.empty() && dq.front() <= i - k)
10 {
11 dq.pop_front(); // 队头已经滑出窗口范围，清理掉
12 }
13 while (!dq.empty() && arr[dq.back()] < arr[i])
14 {
15 dq.pop_back(); // 队尾比新数小，再也不可能是最大值了，清理掉
16 }
17 dq.push_back(i);
18
19 if (i >= k - 1) // 窗口已经凑够k个数，可以记录答案了
20 {
21 result.push_back(arr[dq.front()]); // 队头永远是当前窗口的最大值
22 }
23 }
24 return result;
25}
💡
为什么队尾比新数小就能直接淘汰？假设队尾的数是 x，新数是 y，且 x < y。因为 y 的下标比 x 更靠右，y 会比 x更晚滑出窗口；又因为 y 比 x 大，只要 y 还在窗口里，x 就永远不可能是最大值——x 已经被 y 全面比下去了，留着它毫无意义，直接清理掉。
{1, 3, -1, -3, 5, 3, 6, 7}，k=3 —— 窗口滑动过程
i=0,1,2：1先入队；3比1大，1被淘汰，3入队；-1不比3大，直接入队 —— 窗口凑够3个，最大值是队头3
1
3
-1
-3
5
3
6
7
队头
3
队尾
-1
i=3(值-3)：不比队尾-1大，直接入队 —— 窗口[1,3]最大值仍是队头3
1
3
-1
-3
5
3
6
7
队头
3
-1
队尾
-3
i=4(值5)：队头下标1已滑出窗口[2,4]，弹出；5比-3、-1、3都大，全部淘汰；5入队
1
3
-1
-3
5
3
6
7
队头=队尾
5
i=5(值3)：不比队尾5大，直接入队 —— 窗口[3,5]最大值仍是队头5
1
3
-1
-3
5
3
6
7
队头
5
队尾
3
i=6(值6)：6比3、5都大，全部淘汰；6入队 —— 窗口[4,6]最大值是6
1
3
-1
-3
5
3
6
7
队头=队尾
6
i=7(值7)：7比6大，淘汰；7入队 —— 窗口[5,7]最大值是7
1
3
-1
-3
5
3
6
7
队头=队尾
7
每个窗口的最大值依次是：3, 3, 5, 5, 6, 7——和暴力法逐个比较验证的结果完全一致。注意队列里存活下来的数值始终保持从队头到队尾递减（比如 5, 3、3, -3 这种顺序），这正是"单调"二字的含义。
③ 和单调栈的区别

单调队列和单调栈用的是同一种"维护单调性、提前清理无用数据"的思想，但解决的问题形状不一样：单调栈关心的是"这个数和它两侧最近的更大/更小值"的关系，扫描方向是一条线走到底，元素一旦弹出就永久消失；单调队列关心的是"固定窗口范围内"的最值，窗口会随着扫描不断"滑走"旧数据，所以需要双端操作——队头负责清理"已经滑出窗口"的旧数据，队尾负责清理"被新数据比下去"的数据。

单调栈单调队列
数据结构栈（一端进出）双端队列（两端都能进出）
典型问题找左/右两侧第一个更大/更小的数固定窗口内的最大/最小值
清理时机新数据破坏单调性时新数据破坏单调性时 + 窗口滑出范围时
④ 完整代码与对比

数组长度 n=50，窗口大小 k=10，对比两种做法的操作次数：

n=50, k=10 —— 暴力法 vs 单调队列，操作次数对比
暴力法
410 次
单调队列
95 次
暴力法每滑动一步都要把窗口内 k 个数重新比一遍，总共约 (n-k+1)×k≈410 次；单调队列同样依靠"每个数最多入队一次、出队一次"的均摊分析，总操作次数不超过 2n=100 次，实测 95 次——和 6.1 节单调栈的复杂度证明思路完全一致。k 越大，暴力法的代价越高，单调队列的优势就越明显。
做法核心思路时间复杂度
暴力法每次滑动都重新比较窗口内所有数O(n × k)
单调队列维护递减双端队列，队头即最大值O(n)
🎯
模块六到这里就结束了——单调栈和单调队列都建立在同一个核心技巧上：维护数据的单调性，把"不可能再有用"的数据提前清理掉，避免反复比较。这个思想后面在直方图最大矩形、接雨水、多重背包优化等问题里都会反复出现。遇到"找某个方向上第一个更大/更小的值"，先想单调栈；遇到"固定窗口内的最值"，先想单调队列。