单调栈：高效求解下一个更大元素的算法解析

核心逻辑与数学原理

单调栈（Monotonic Stack）是一种通过维护内部元素的单调性，以时间换空间，实现 $O(N)$ 扫描的线性数据结构。其核心逻辑在于及时排除不可能成为答案的冗余决策，从而将原本需要 $O(N^2)$ 的双重循环优化至均摊 $O(1)$。

以求解“下一个更大元素（Next Greater Element, NGE）”为例。定义序列 $A$ 的长度为 $N$。对于任意位置 $i$，我们需要找到最小的 $j$ 满足 $j > i$ 且 $A[j] > A[i]$。在线性扫描过程中，若存在 $x < y$ 且 $A[x] \\le A[y]$，那么对于 $x$ 左侧的任意元素而言，$A[x]$ 绝不可能成为其“下一个更大元素”，因为 $A[y]$ 距离更近且值更大。此时 $A[x]$ 成为冗余决策，应当被立即弹出。

数学归纳证明：单调栈内部维护的是尚未找到答案的元素下标。设栈内元素下标从栈底到栈顶依次为 $p_1, p_2, \\dots, p_k$。则必有：

$$ p_1 < p_2 < \dots < p_k $$

$$ A[p_1] \ge A[p_2] \ge \dots \ge A[p_k] $$

当新元素 $A[i]$ 入栈时，若 $A[i] > A[p_k]$，则 $p_k$ 的后继最大值即为 $i$。弹出 $p_k$，继续比对 $p_{k-1}$，直到栈空或满足单调性后将 $i$ 压入。每个元素至多入栈一次、出栈一次，总时间复杂度严格为 $O(N)$。

状态设计与算法推导

在具体实现中，栈内通常存储元素下标而非元素数值。因为下标既能通过 $A[idx]$ 索引数值，又能直接计算区间长度（如求解最大矩形面积时）。

算法流程推导（以右侧第一个更大元素为例）：

初始化一个空栈 st，设计一个答案数组 ans 全部初始化为 -1。
从左到右遍历序列 $A$，当前位置为 $i$。
循环判定：若栈不为空且 $A[i] > A[\text{st.top()}]$，说明当前元素是栈顶元素的“下一个更大元素”。
- 记录答案：$\text{ans}[\text{st.top()}] = A[i]$（或存储下标 $i$）。
- 弹出栈顶：$\text{st.pop()}$。
- 重复此步骤，直到栈空或 $A[i] \\le A[\text{st.top()}]$。
将当前下标 $i$ 压入栈中：$\text{st.push}(i)$。
遍历结束，栈内剩余元素的 ans 仍为 -1，表示右侧没有更大元素。

若需求“左侧第一个更小元素”，只需将遍历方向改为从左到右，并将弹出条件修改为 $A[i] \\le A[\text{st.top()}]$ 维护单调递增栈即可。本质是利用符号的对偶性。

C++ 标准源码（NOIP 风格）

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

// 求解每个元素右侧第一个严格更大元素的下标，若不存在则为 -1
vector<int> getNextGreaterElement(const vector<int>& A) {
    int n = A.size();
    vector<int> ans(n, -1);
    stack<int> st; // 栈内存储下标，从栈底到栈顶对应的元素值严格单调递减

    for (int i = 0; i < n; ++i) {
        // 必须使用 while 循环持续消除所有小于当前元素的栈顶冗余
        while (!st.empty() && A[i] > A[st.top()]) {
            ans[st.top()] = i; // 记录触发弹出的当前下标即为答案
            st.pop();
        }
        st.push(i); // 当前下标必须入栈，作为后续元素的潜在比对目标
    }
    return ans;
}

int main() {
    // 提升 IO 性能，防止在 NOIP 大数据量下因 std::endl 或 cin 导致 TLE
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

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

    vector<int> ans = getNextGreaterElement(A);

    for (int i = 0; i < n; ++i) {
        // 输出对应的元素值，若不存在输出 -1
        if (ans[i] != -1) {
            cout << A[ans[i]] << (i == n - 1 ? "" : " ");
        } else {
            cout << -1 << (i == n - 1 ? "" : " ");
        }
    }
    cout << "\n";

    return 0;
}

NOIP 实战避坑指南

栈空状态的越界检查（Segment Fault） 在 while 循环判定弹出条件时，必须将 !st.empty() 放在逻辑与 && 的最左侧。若先访问 A[st.top()] 再判断栈空，在栈为空时会导致非法内存访问，直接引发评测机返回 RE（运行时错误）。
符号连续相等的死循环与逻辑错误 注意“大于” $A[i] > A[\text{st.top()}]$ 与“大于等于” $A[i] \\ge A[\text{st.top()}]$ 的边界选择。如果题目要求严格大于，而你错误地写成了 $\ge$，会导致元素被错误弹出。而在某些变体题目中（如计算矩形面积），若处理相同高度元素时未正确设计弹出逻辑，可能导致无法退出 while 循环，引发 TLE 甚至死循环。
空间开销优化（数组模拟栈） STL 的 std::stack 底层默认是 std::deque，频繁内存分配有常数开销。在 NOIP 极限时限下，推荐使用原生数组模拟栈：int st[MAXN], top = 0;。用 st[++top] = i 代替 push，用 top-- 代替 pop。这能带来近 3 倍的常数级加速。

经典 NOIP/洛谷真题

1. 洛谷 P5788 【模板】单调栈

题意描述：给定一个长度为 $N$ 的正整数序列，输出每个数后面第一个比它大的元素的下标。$N \le 3 \times 10^6$。
问题本质与核心思路：标准单调栈模板题。由于数据量达到 $3 \times 10^6$，必须使用原生数组模拟栈，并使用 scanf 或快读（Fast IO）。维护一个单调递减栈（存储下标），当新元素大于栈顶对应元素时，该新元素下标即为栈顶元素的答案。

2. 洛谷 P1191 矩形

题意描述：给出一个 $N \times N$ 的 $01$ 矩阵，求全为 $1$ 的子矩形个数。$N \le 400$。
问题本质与核心思路：二维单调栈问题。通过悬线法思想，预处理出每个点向上连续的 $1$ 的个数，作为当前行该位置的“高度”。对于每一行，问题转化成求直方图中的子矩形数量。利用单调栈在 $O(N)$ 时间内找到每个位置左右第一个比它矮的位置，即可通过数学组合公式在总时间复杂度 $O(N^2)$ 内秒杀，避免了 $O(N^4)$ 的暴力枚举。