单调队列（上）

来源：算法讲解054【必备】单调队列-上　·　2026-10-20

依据：视频字幕 2000 字

一句话概括

单调队列 = 一个双端队列，维护“窗口内元素的单调性”，使得在窗口左右端都只前进不回退的滑动过程中，O(1) 取窗口最大/最小值，总代价 O(n)。

它解决什么问题

滑动窗口（L、R 只增不减，窗口是左闭右开 [L, R)）在滑动过程中，每个时刻都要能立刻回答窗口内的最大值或最小值。暴力每次扫窗口是 O(窗口长)，总 O(n·k)；单调队列把它压到总 O(n)。

基础知识（前置概念，用大白话解释）

队列：先进先出，一头进一头出。
双端队列 deque：两头都能进、都能出。单调队列真正用的是它——右端进新元素，两端都可能出元素。
滑动窗口：用两个指针 L、R 表示区间 [L, R)。R++ 表示右边吞进一个数，L++ 表示左边吐出一个数。L、R 都不回退，这是单调队列能成立的关键前提。
单调性：队列里存的下标对应的值，从队头到队尾保持单调（求最大值时单调递减，求最小值时单调递增）。

原理（为什么这么做是对的，尽量给直觉）

求窗口最大值。核心观察：如果新来的数 x 比队尾的数还大（或相等），那么队尾那个数永远不可能再成为最大值了——因为 x 比它大，而且 x 比它晚过期（下标更大，出窗口更晚）。所以队尾那个数可以直接扔掉。

于是队列里剩下的下标，对应的值从队头到队尾单调递减。队头就是当前窗口最大值。

淘汰可能性有两个口：

队尾淘汰：新元素进来时，把队尾所有“又小又老”的元素弹掉（它们被新元素完全压制）。
队头淘汰：窗口左边界前进时，如果队头下标已经 < L（过期了），从队头弹掉。

对比单调栈只有一个口（栈顶）淘汰，单调队列有两个口，所以思想上更难一点，但经典用法反而简单。

正确性直觉：队列里永远只保留“还有可能成为未来某个时刻最大值”的候选，被压制的、过期的都被清掉，队头自然就是当前答案。

步骤（编号，可照着写）

以求窗口最大值为例，窗口 [L, R)，遍历 R 从 0 到 n-1：

右端进：当队列非空且 a[队尾下标] <= a[R]，弹出队尾（新元素压制旧的）。然后 R 入队尾。
左端出：如果队头下标 < L（已过期），弹出队头。（通常写成 if，因为一次 L 只前进一格时最多过期一个；若 L 一次跳多格要用 while。）
取答案：此时队头下标对应的值就是当前窗口最大值。
按题目要求移动 L（比如窗口长度固定为 k 时，R >= k-1 后每步 L++ 并输出答案）。

样例（一个具体小例子，带每步变化）

数组 a = [5, 2, 6, 3]，窗口长度 k=3，求每个窗口最大值。队列存下标。

R=0，a=5：队空，入队 → 队列 [0]。窗口未满。
R=1，a=2：队尾 a[0]=5 > 2，不弹，入队 → [0,1]。窗口未满。
R=2，a=6：队尾 a[1]=2 ≤ 6 弹；队尾 a[0]=5 ≤ 6 弹；入队 → [2]。窗口 [0,3) 满，队头 2 → 最大值 6。
L 移到 1。R=3，a=3：队尾 a[2]=6 > 3，不弹，入队 → [2,3]。检查队头 2 ≥ L=1，不过期。窗口 [1,4)，队头 2 → 最大值 6。

结果：[6, 6]。

代码（Python 一份：好读、用于理解；C++ 一份：竞赛风，能直接抄进比赛，带注释，不用玄学宏）

Python（用 collections.deque，好读版）：

from collections import deque

def window_max(a, k):
    dq = deque()          # 存下标，值单调递减
    res = []
    for r, x in enumerate(a):
        # 右端进：弹掉队尾所有 <= x 的
        while dq and a[dq[-1]] <= x:
            dq.pop()
        dq.append(r)
        # 左端出：队头过期
        l = r - k + 1
        if dq[0] < l:
            dq.popleft()
        # 窗口满则记录
        if l >= 0:
            res.append(a[dq[0]])
    return res

C++（竞赛风，数组模拟双端队列，直接抄）：

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

// 求每个长度 k 的窗口最大值，返回结果数组
vector<int> windowMax(const vector<int>& a, int k) {
    int n = a.size();
    vector<int> q(n);          // 存下标，手写双端队列
    int head = 0, tail = 0;    // 队列区间 [head, tail)
    vector<int> res;
    for (int r = 0; r < n; ++r) {
        // 右端进：队尾值 <= 当前值就弹掉
        while (head < tail && a[q[tail - 1]] <= a[r]) --tail;
        q[tail++] = r;
        // 左端出：队头过期（窗口左界 l = r-k+1）
        int l = r - k + 1;
        if (q[head] < l) ++head;
        // 窗口满则记录答案
        if (l >= 0) res.push_back(a[q[head]]);
    }
    return res;
}

复杂度（时间/空间，最好/平均/最坏，顺带说常数大不大）

时间：每个下标最多进队一次、出队一次，均摊 O(n)。最好/平均/最坏都是 O(n)（均摊分析，单次操作可能 O(k) 但总代价 O(n)）。
空间：队列最多存 n 个下标，O(n)（若窗口长 k，实际队列长度 ≤ k）。
常数：很小。手写数组双端队列比 std::deque 快，竞赛里推荐手写。

竞赛里什么时候用（看到什么题面特征就该想到它）

题面出现“滑动窗口”“长度为 k 的连续子段”的最大/最小值。
“窗口左右端只前进不回退”的区间最值查询。
求“每个位置左边/右边第一个比它大/小的数”且带距离限制（和单调栈区分：单调栈无窗口过期，单调队列有 L 过期）。
动态规划转移里出现 dp[i] = max/min(dp[j] + ...)，j 的范围是一个滑动区间——这是下节课的拓展用法，看到这种形式就该想到单调队列优化。

竞赛模板（C++，可直接背下来的写法；变量名清楚）

// 通用模板：窗口 [l, r) 滑动，维护最大值
// 用法：把下面循环体套进你的主循环，按需改 <= 为 <（处理重复值）
int head = 0, tail = 0;
vector<int> q(n);              // 存下标
for (int r = 0; r < n; ++r) {
    while (head < tail && a[q[tail - 1]] <= a[r]) --tail;  // 队尾淘汰
    q[tail++] = r;
    int l = r - k + 1;                                     // 窗口左界
    if (q[head] < l) ++head;                               // 队头淘汰
    if (l >= 0) { /* 此时 a[q[head]] 是窗口最大值 */ }
}
// 求最小值：把 <= 改成 >= 即可

边界与易错点（WA 的常见原因，越具体越好）

队列存下标还是存值：必须存下标，否则无法判断队头是否过期（q[head] < l）。存值就废了。
队头淘汰用 if 还是 while：L 每步只前进一格时用 if 够；若 L 一次跳多格（比如按条件跳），必须用 while (head < tail && q[head] < l) ++head;。
<= 还是 <：求最大值时队尾弹 <=（相等也弹，保留新的，因为新的更晚过期）；若题目要求保留最早出现的相等元素，改成 <。想清楚再写。
窗口未满就输出：l = r-k+1 可能为负，必须 if (l >= 0) 才记录答案，否则前 k-1 个位置会多输出。
空队列访问队头：q[head] 前要保证 head < tail。上面的流程里入队后队列必非空，但自己改逻辑时容易漏。
下标从 0 还是 1 开始：手写队列 head/tail 从 0 开始，别和题目 1-indexed 混。
多组数据没清空队列：head = tail = 0 要重置。

同类题 / 变形（说清楚怎么改）

求最小值：队尾淘汰条件 <= 改 >=，队列变单调递增，队头即最小值。
窗口长度不固定（比如和约束为 S 的最短子数组）：L 按条件前进，队头淘汰改 while。
二维滑动窗口最值（如矩阵中 k×k 子矩阵最值）：先对每行做一遍单调队列，再对结果的每列做一遍，两趟 O(nm)。
单调队列优化 DP：转移 dp[i] = min_{j in [i-k, i-1]} dp[j] + w(i)，把 dp[j] 放进单调队列，队头取最优。这是下节课内容。
和单调栈的区分：单调栈解决“左右第一个更大/更小”，无过期；单调队列多了“窗口左界过期”这一维。

常见坑

把单调队列当成“普通队列 + 排序”，那是 O(n log n)，丢了 O(n) 的意义。
忘记“L、R 不回退”这个前提，拿它去做任意区间 RMQ——那要用线段树/ST 表。
队尾弹的时候比较的是 a[q[tail-1]] 而不是 q[tail-1]，别拿下标比大小。
输出答案的时机：在“右端进 + 左端出”都做完之后再取队头，顺序错了会取到过期元素。

拓展（变体、实际用途、面试常问）

变体：单调队列 + 二分（如“长度至少 L 的最大平均值”配合前缀和）、单调队列优化多重背包。
实际用途：实时数据流的滑动窗口统计（限流、监控指标）、图像处理的滑动窗口滤波。
面试常问：“滑动窗口最大值”（LeetCode 239）几乎是单调队列的代名词；追问“为什么是 O(n)”“和优先队列比优劣”（优先队列 O(n log n) 且删除懒，单调队列更优）。

自测 3 题（题目 + 折叠答案）

题 1：数组 [1,3,-1,-3,5,3,6,7]，k=3，求每个窗口最大值。

答案

[3,3,5,5,6,7]。手推：窗口 [1,3,-1]→3；[3,-1,-3]→3；[-1,-3,5]→5；[-3,5,3]→5；[5,3,6]→6；[3,6,7]→7。

</details>

题 2：把上面代码改成求最小值，需要改哪几处？

答案

两处：① 队尾淘汰条件 a[q[tail-1]] <= a[r] 改成 >=（弹掉队尾所有比新元素大的，队列变单调递增）；② 取答案仍是 a[q[head]]（队头即最小）。其余不变。

</details>

**题 3