高效单调栈与单调队列的核心原理与应用解析

核心逻辑与数学原理

单调栈与单调队列是维护元素单调性的线性数据结构。其核心物理模型是动态转折点剔除与生存期淘汰。

在单调栈中，新元素的加入会破坏原有的单调性。若要求栈内元素单调递增，当新元素 $x$ 小于栈顶元素时，栈顶元素在后续的比较中已被 $x$ 完全遮挡（或替代），失去作为最优解的可能，必须立即弹出。每个元素至多入栈一次、出栈一次，均摊时间复杂度为 $O(N)$。

在单调队列中，引入了“生存期”概念，即滑动窗口的边界约束。单调队列维护的是一个双端队列，其核心物理模型是区间最值（RMQ）的动态演进。对于两个元素 $A[i]$ 和 $A[j]$，若 $i < j$ 且 $A[i] ext{ ≤ } A[j]$，在窗口向右滑动时，$A[i]$ 无论在大小还是生存期上都已被 $A[j]$ 支配。因此，$A[i]$ 成为无用冗余，需从队尾剔除。同时，队头元素若超出窗口左边界 $L = i - K + 1$，则因过期而从队头弹出。

状态设计与算法推导

1. 单调栈：下一个更大元素（Next Greater Element）

设输入序列为 $A$，目标是求解每个位置 $i$ 右侧第一个大于 $A[i]$ 的元素下标 $R[i]$。

• 状态设计：栈内存储元素下标。从左到右遍历序列。
• 转移与淘汰策略： 当前遍历到 $A[i]$。当栈不为空且 $A[i] > A[ ext{stk.top()}]$ 时，说明 $A[i]$ 是栈顶元素右侧第一个比它大的数。 触发状态更新：

$$R[ ext{stk.top()}] = i$$

执行弹出操作 $ ext{stk.pop()}$，重复此过程直到栈空或 $A[i] ext{ ≤ } A[ ext{stk.top()}]$。最后将 $i$ 压入栈中。

2. 单调队列：滑动窗口最值

设窗口大小为 $K$，求解每个位置 $i$ 结束的窗口内的最大值。

• 状态设计：双端队列 q 存储元素下标，满足 $A[ ext{q.front()}] ext{ ≥ } A[ ext{q.back()}]$。
• 推导逻辑：

1. 队头去过期：当前下标为 $i$，若 $ ext{q.front()} < i - K + 1$，说明队头最值已滑出窗口，执行 q.pop_front()。
2. 队尾去冗余：当队列不为空且 $A[i] ext{ ≥ } A[ ext{q.back()}]$ 时，队尾元素由于值较小且生存期更短，沦为死节点，执行 q.pop_back()。
3. 入队与决策：将 $i$ 压入队尾。当 $i ext{ ≥ } K - 1$ 时，当前窗口最大值即为 $A[ ext{q.front()}]$。

C++ 标准源码

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

// 模拟洛谷 P5788 【模板】单调栈
void solveMonotoneStack() {
    int n;
    if (!(cin >> n)) return;

    vector<int> a(n + 1);
    vector<int> r(n + 1, 0);
    vector<int> stk; 
    stk.reserve(n + 1); // 预分配内存，规避 vector 动态扩容带来的常数开销

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    for (int i = 1; i <= n; ++i) {
        // 关键点：严格大于时触发弹出，栈内存储下标而非具体数值
        while (!stk.empty() && a[i] > a[stk.back()]) {
            r[stk.back()] = i;
            stk.pop_back();
        }
        stk.push_back(i);
    }

    for (int i = 1; i <= n; ++i) {
        cout << r[i] << (i == n ? "" : " ");
    }
    cout << "\n";
}

// 模拟洛谷 P1886 滑动窗口 /【模板】单调队列
void solveMonotoneQueue() {
    int n, k;
    if (!(cin >> n >> k)) return;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

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

    // 1. 求区间最小值
    for (int i = 0; i < n; ++i) {
        // 队头检查：剔除超出滑动窗口左边界的过期下标
        if (!q.empty() && q.front() < i - k + 1) {
            q.pop_front();
        }
        // 队尾检查：新元素更小，老元素既大又旧，直接淘汰
        while (!q.empty() && a[i] <= a[q.back()]) {
            q.pop_back();
        }
        q.push_back(i);

        if (i >= k - 1) {
            cout << a[q.front()] << (i == n - 1 ? "" : " ");
        }
    }
    cout << "\n";
}

int main() {
    // 优化标准流输入输出性能，禁止与 stdio 同步，避免被卡常数
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // 根据评测目标切换调用，此处仅作演示
    solveMonotoneStack();

    return 0;
}

NOIP 实战避坑指南

1. 单调队列队头越界与死循环 在处理滑动窗口移动时，初学者常错写为 if (q.front() == i - k)。这种精确匹配在处理非步长为 1 的动态区间移动，或者中途存在非标数据跳跃时会导致漏判，使队列中残留已过期的非法下标，引发逻辑错误甚至数组越界访问。正确做法是使用严格不等式判断：`if (q.front() < i - k + 1)。此外，在使用while弹出队尾时，必须先检查!q.empty()，否则在空队列上调用back()` 会导致 Undefined Behavior（段错误或死循环）。
2. 空间开销与下标错位 单调栈、单调队列存储的一定是下标而非权值本身。若错误地存储了权值，将无法进行生存期检查（无法获知该元素是否滑出窗口），也无法精确定位下一个更大元素的位置。单调栈数组大小必须与原序列大小 $N$ 严格一致。在 NOIP/Linux 环境下，若使用标准 std::deque，其内部内存块分段分配，带有较大的常数时间开销。在时限较紧（如 1.0s 内处理 $10^6$ 数据）的题目中，应当改用数组模拟双端队列（用 head 和 tail 指针维护），以达到极致的 O2 编译优化表现。

经典 NOIP/洛谷 真题

1. 洛谷 P2866 [USACO06NOV] Bad Hair Day S

• 题意描述：$N$ 头奶牛排成一列，每头牛向右看。已知每头牛的身高。一头牛能看到所有在它右边、且高度严格小于它的奶牛，直到被一头高度大于或等于它的奶牛挡住为止。求所有奶牛能看到的奶牛总数。
• 问题本质：求每个元素右侧第一个大于等于它的元素位置。
• 核心解题思路： 传统思维是计算每头牛能看到多少头牛，这需要从右往左维护单调栈。物理模型可逆向转换为：一头牛能被左边多少头牛看到。 从左到右遍历奶牛，维护一个自栈底到栈顶严格单调递减的单调栈。当新牛 $i$ 准备入栈时，若栈顶牛的高度小于或等于当前牛 $i$，说明栈顶牛无法跨越当前这头高牛向右看，栈顶牛的生存期结束，执行弹出。弹出完毕后，栈内剩余的牛高度均大于当前牛 $i$，说明它们都能看到当前牛 $i$。此时栈内元素个数即为当前牛能被看到的次数，直接累加到答案中。最后将 $i$ 入栈。需要注意，最终答案最大可能达到 $rac{N(N-1)}{2}$，必须使用 long long 存储。

2. 洛谷 P1419 寻找段落

• 题意描述：给定一个长度为 $N$ 的序列 $A$，求一个长度在 $[S, T]$ 之间的连续子段，使得该子段内元素的平均值最大。
• 问题本质：分数规划 + 单调队列优化 DP（区间和前缀和转化）。
• 核心解题思路： 最大化平均值通常采用二分答案。设当前二分的平均值为 $mid$，则每个元素减去 $mid$，问题转化为是否存在一个长度在 $[S, T]$ 之间的子段，其和大于等于 0。 令 $B[i] = A[i] - mid$，计算 $B$ 的前缀和序列 $Sum$。子段和可表示为 $Sum[r] - Sum[l-1]$，其中约束条件为 $S ext{ ≤ } r - l + 1 ext{ ≤ } T$，变形得 $r - T ext{ ≤ } l - 1 ext{ ≤ } r - S$。 当固定右端点 $r$ 时，目标是最大化 $Sum[r] - Sum[l-1]$，即寻找左端点 $l-1$ 使得 $Sum[l-1]$ 最小。$l-1$ 的可行区间是 $[r - T, r - S]$。这是一个典型的滑动窗口最值问题。 使用单调队列维护前缀和序列 $Sum$ 在滑动窗口 $[r - T, r - S]$ 内的最小值。随着 $r$ 的右移，窗口同步右移。若在任意时刻满足 $Sum[r] - Sum[ ext{q.front()}] ext{ ≥ } 0$，则说明当前 $mid$ 可行，调整二分下界；否则调整上界。单调队列成功将每次二分的检验复杂度由 $O(N^2)$ 降至 $O(N)$。