高效区间最值维护：单调队列的核心原理与实现指南

核心逻辑与数学原理

以求解经典的“滑动窗口最大值（Sliding Window Maximum）”为例。 定义一个长度为 $N$ 的序列 $A$，窗口大小为 $K$。随着窗口右端点 $i$ 从 $1$ 到 $N$ 线性扫描，需要动态获取当前有效窗口 $[i - K + 1, i]$ 内的最大值。

单调队列（Monotonic Queue）作为一种维护区间最值的线性数据结构，其核心思想在于利用时序与大小的双重单调性，及时排除冗余决策。 总时间复杂度从原本暴力解法的 $O(N \cdot K)$ 优化至 $O(N)$。

在单调队列中，核心的淘汰逻辑可以总结为“青年才俊原则”：

“随着窗口右端点 i 的线性扫描，队列里存放的是有资格竞争未来最值的‘候选决策点’（下标）。 新元素入队时，会触发无情的淘汰机制。 如果一个留在队中的老决策，生得比你早（下标小，意味着生存期剩得短），长得还没你帅（数值不比你优秀），那么在它仅剩的生命周期里，由于你的存在，它永远不可能成为区间最值。 这个“既老又弱”的决策就沦为了绝对冗余，必须立即被无情剔除。

基于这一原则，新元素入队时会从队尾掀起连续的“弹队”风暴，直到队列恢复“下标严格递增、数值严格递减”的双重单调性。 在该机制下，每一个下标元素一辈子“至多入队一次，至多出队一次”，因此其单步操作在全局视角的均摊复杂度为严格的 $O(1)$。

状态设计与对偶变体

单调队列一律存储元素下标。因为下标不仅能通过 $A[\text{index}]$ 索引数值，还能通过 $i - \text{index} \ge K$ 瞬间判定该决策是否因生命周期终结而失效。

通过微调队尾弹栈符号，可以任意切换求区间最大值或最小值：

核心算法模板

// 核心逻辑：单调队列维护滑动窗口最值核心片段（以区间最大值为例）
// q[] 模拟双端队列存储下标，head = 1, tail = 0 初始化为空队列
int head = 1, tail = 0;
for (int i = 1; i <= n; ++i) {
    // 1. 队头合法性检查：弹出离开滑动窗口边界的失效元素
    if (head <= tail && q[head] <= i - k) {
        head++;
    }
    // 2. 队尾单调性维护：剔除数值无优势且位置靠前的冗余决策
    while (head <= tail && a[q[tail]] <= a[i]) {
        tail--;
    }
    // 3. 当前新决策入队（延续其生存期潜力）
    q[++tail] = i;

    // 4. 业务结算：当窗口完全成型（i >= k）时，队头即为当前窗口最值
    if (i >= k) {
        ans[i] = a[q[head]];
    }
}

队内状态不变性证明（Invariant Proof）

以区间最大值（维护单调递减队列）为例。 设在任意扫描时刻，队列内从队头到队尾存储的元素下标依次为 $q[\text{head}], q[\text{head}+1], \dots, q[\text{tail}]$。我们通过数学归纳法证明该结构死锁了以下两个状态不变性：

• 不变性一（下标严格递增且合法）：$i - K + 1 \le q[\text{head}] < q[\text{head}+1] < \dots < q[\text{tail}] = i$
• 不变性二（数值严格单调递减）：$A[q[\text{head}]] > A[q[\text{head}+1]] > \dots > A[q[\text{tail}]]$

1. 初始状态：遍历前队列为空，不变性显然成立。当扫描到第一个元素 $i=1$ 时，入队后仅有一项，两个不变性依然成立。
2. 递推（状态转移）：假设当前队列满足上述不变性，此时新元素 $i$（必有 $i > q[\text{tail}]$）到来：

• 步骤 A（队头过界剔除）：检查队头。若 $q[\text{head}] < i - K + 1$，说明旧队头生命周期已到，执行 head++。由于原队列下标严格递增，剔除后剩余部分的下标仍合法且递增，数值依然保持严格单调递减。
• 步骤 B（队尾去劣弹队）：新元素 $A[i]$ 尝试从队尾入队。激活 while 循环：若 $A[q[\text{tail}]] \le A[i]$，说明队尾元素不仅比 $A[i]$ 矮，而且由于 $q[\text{tail}] < i$，它还会比 $A[i]$ 更早滑出窗口。它在未来绝无成为最大值的可能，属于冗余决策，执行 tail-- 弹出。
• 步骤 C（新元素履约）：当 while 循环终止时，队尾留下的元素必然满足 $A[q[\text{tail}]] > A[i]$（或者队列弹空）。此时将 $i$ 压入队尾（q[++tail] = i）。新状态下，下标维有 $q[\text{tail}-1] < i$，数值维有 $A[q[\text{tail}-1]] > A[i]$。两个不变性在动态调整后，再次完美恢复。

NOIP 实战避坑指南

数组模拟双端队列的指针初始化

手写数组模拟双端队列时，常用的初始化格式为 int head = 1, tail = 0;。

• 当 head > tail 时代表队列为空。
• 插入第一个元素时执行 q[++tail] = i;，此时 head == tail == 1，队列开始具备首个决策。
• 严禁将初始化误写为 head = 0, tail = 0，这会导致程序在空队列判断时产生逻辑混乱。

严格最值去劣中的“等于号”符号陷阱

在队尾单调性维护时，条件究竟用 > 还是 >=？ 在标准滑动窗口中，强烈建议使用带有等于号的 a[q[tail]] <= a[i]（求最大值）或 a[q[tail]] >= a[i]（求最小值）。

教练一句话点睛： “如果两个元素数值完全相同，后来的元素 $i$ 无论如何都比先来的 $q[\text{tail}]$ 拥有更长的‘寿命’（更晚断气）。把相等的旧决策弹掉，用新决策替代，能让队列规模更精简，并极大程度延长最值候选的时间线，防止冗余元素堆积。”

规避 std::deque 的巨大常数

NOIP 极其看重运行效率。标准库中的 std::deque 并非采用连续内存存储，其内部涉及指针重载与高频的动态内存分配，常数巨大。在 $10^6$ 级别的数据量下，手写数组 q[MAXN] 配合 head++、tail-- 操作没有一点额外开销，运行效率比 STL 稳步提升 3 倍以上。

经典真题讲解

1. 洛谷 P1886 滑动窗口 /【模板】单调队列

• 题意描述：给定一个长度为 $n$ 的数组和一个大小为 $k$ 的窗口，求每次移动后窗口中的最大值和最小值。$n \le 10^6$。
• 真题本质：标准的单调队列静态区间最值维护。

核心算法实现

// 核心逻辑：单调队列双向扫描基准线
// 求最小值：维护严格单调递增队列
int head = 1, tail = 0;
for (int i = 1; i <= n; ++i) {
    if (head <= tail && q[head] <= i - k) head++;
    while (head <= tail && a[q[tail]] >= a[i]) tail--; // 剔除大值
    q[++tail] = i;
    if (i >= k) min_ans[i] = a[q[head]];
}

// 求最大值：维护严格单调递减队列
head = 1, tail = 0;
for (int i = 1; i <= n; ++i) {
    if (head <= tail && q[head] <= i - k) head++;
    while (head <= tail && a[q[tail]] <= a[i]) tail--; // 剔除小值
    q[++tail] = i;
    if (i >= k) max_ans[i] = a[q[head]];
}

2. 洛谷 P2216 [HAOI2007] 理想正方形

• 题意描述：给定一个 $a \times b$ 的整数矩阵，从中找出一个 $n \times n$ 的正方形区域，使得该区域内的最大值与最小值的差最小。$a, b \le 1000, n \le a, b$。
• 真题本质：二维滑动窗口最值，一维单调队列正交分解的典范。
• 解题核心：
• 行向降维：对矩阵的每一行独立跑一次长度为 $n$ 的滑动窗口，求出各行每个长为 $n$ 的横向区间的最大值与最小值，结果存于辅助矩阵 row_max[i][j] 与 row_min[i][j]。
• 列向收敛：在行降维的基础之上，对辅助矩阵的每一列独立跑一次长度为 $n$ 的滑动窗口。此时，row_max 的纵向窗口最大值即为二维 $n \times n$ 区域的全局最大值，row_min 同理。整个算法在 $O(a \times b)$ 内优雅破局。

核心算法实现

// 核心逻辑：以计算二维最大值为例，row_max[i][j] 表示第 i 行闭区间 [j-n+1, j] 的最大值
// 1. 横向扫描：处理每一行的一维窗口
for (int i = 1; i <= a; ++i) {
    int head = 1, tail = 0;
    for (int j = 1; j <= b; ++j) {
        if (head <= tail && q[head] <= j - n) head++;
        while (head <= tail && mat[i][q[tail]] <= mat[i][j]) tail--;
        q[++tail] = j;
        if (j >= n) row_max[i][j] = mat[i][q[head]];
    }
}

// 2. 纵向扫描：在行最值矩阵的基础上处理每一列的一维窗口
int final_ans = 2e9; 
for (int j = n; j <= b; ++j) { // 仅处理有效的纵向列
    int head = 1, tail = 0;
    for (int i = 1; i <= a; ++i) {
        if (head <= tail && q[head] <= i - n) head++;
        while (head <= tail && row_max[q[tail]][j] <= row_max[i][j]) tail--;
        q[++tail] = i;
        if (i >= n) g_max[i][j] = row_max[q[head]][j]; // 此时已获得二维正方形内的最大值
    }
}
// 最小值处理同理，最后遍历所有合法的 (i, j) 刷新全局最小差值：final_ans = min(final_ans, g_max[i][j] - g_min[i][j])