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

核心逻辑与数学原理

以求解“右侧下一个更大元素（Next Greater Element, NGE）”为例。 定义序列 $A$ 长度为 $N$。对于任意位置 $i$，需找到最小的 $j$ 满足 $j > i$ 且 $A[j] > A[i]$。

单调栈作为一种通过维护栈内元素单调性实现 $O(N)$ 扫描的线性数据结构，其核心思想在于利用时序与大小的双重单调性，及时处理或排除决策，将总时间复杂度从原本暴力解法的 $O(N^2)$ 彻底优化至 $O(N)$。

在该机制下，每一个决策元素一辈子“至多入栈一次，至多出栈一次”，因此其单步操作在全局视角的均摊复杂度为 $O(1)$。

从左向右扫描的“及时履约”逻辑

当我们从左到右遍历序列时，栈内存放的是尚未找到右侧更大元素的单调递减候选项。

• 当遍历到 $A[i]$ 时，如果 $A[i] > A[\text{栈顶}]$，说明当前元素 $A[i]$ 就是栈顶元素苦苦寻找的“右侧第一个更大元素”。
• 此时栈顶元素“履约成功”，记录答案并将其弹出。继续比对新的栈顶，直到栈空或不再满足大于关系。最后将 $i$ 压入栈中。

状态设计与对偶变体

在信息学竞赛中，单调栈一律存储元素下标而非数值。因为下标既能通过 $A[idx]$ 索引数值，又能直接通过下标作差（$i - j$）计算区间长度。

通过统一采用从左到右的扫描方向，仅需微调弹栈触发条件与答案结算时机，即可完美解决全部四种对偶问题。这种分类方式将单调栈抽象为两大核心机理：

核心算法模板

// 核心逻辑：从左到右扫描，求解每个元素右侧第一个严格更大元素的下标
// st[] 模拟栈，top = 0 表示栈空；ans[] 存储答案，未找到则默认为 0
int top = 0;
for (int i = 1; i <= n; ++i) {
    // 当栈不为空且当前元素大于栈顶对应元素时，触发弹栈
    while (top > 0 && a[i] > a[st[top]]) {
        ans[st[top]] = i; // 结算：栈顶元素的右侧第一个更大元素就是当前位置 i
        top--;            // 弹栈
    }
    st[++top] = i;        // 当前位置入栈，等待它的未来履约人
}

栈内状态不变性证明

设在算法运行的任意阶段，栈内从栈底到栈顶的元素下标依次为 $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]$

1. 初始状态：扫描前栈为空，不变性显然成立。当压入第一个元素 $p_1$ 时，栈内仅有一项，两个不变性依然成立。
2. 递推（状态转移）：假设当前栈内状态满足上述两个不变性。此时新元素 $i$（必有 $i > p_k$）到来：

• 情况 A：若 $A[i] \le A[p_k]$，根据代码逻辑，不触发 while 循环，$i$ 直接被压入栈顶。新状态下，下标维有 $p_k < i$，数值维有 $A[p_k] \ge A[i]$。两个不变性完美维持。
• 情况 B：若 $A[i] > A[p_k]$，进入 while 循环开始弹栈。每弹出一个元素 $p_{\text{top}}$，都在逻辑上宣告：“$A[i]$ 是 $A[p_{\text{top}}]$ 右侧遇到的第一个更大元素”，记录答案并成功结算。当 while 循环终止时，要么栈被清空（退化为初始状态），要么遇到的新栈顶满足 $A[p_{\text{new\_top}}] \ge A[i]$。此时再将 $i$ 压入，两个不变性在经历动态调整后，依然完美恢复。

NOIP 实战避坑指南

数组模拟栈的边界控制

使用 int st[MAXN], top = 0; 时，必须确保 top > 0 才能访问 st[top]。在 while 循环中，必须将 top > 0 放在 && 的最左侧。若由于逻辑短路写错顺序（形如 while(a[i] > a[st[top]] && top > 0)），当栈空时会优先访问 a[st[0]] 甚至 a[st[-1]]，导致 Runtime Error (RE)。

严格最值与非严格最值的符号陷阱

根据题意严密确立 > 还是 >=：

• 求严格大于：触发弹栈条件为 a[i] > a[st[top]]。
• 求非严格大于（大于等于）：触发条件为 a[i] >= a[st[top]]。 若在需要严格单调的变体题中（如柱状图最大矩形）错用符号，会导致相同高度元素处理逻辑多算或漏算边界，直接导致 WA。

内存与常数优化

stack底层默认是deque，涉及动态内存分配，在大数据量下常数极大。手写st[++top] = i和top--` 没有任何额外开销，运行速度比 STL 快 3 倍以上。

经典真题讲解

洛谷 P5788 【模板】单调栈

• 题意简述：给定一个长度为 $N$ 的正整数序列，输出每个数后面第一个比它大的元素的下标。$N \le 3 \times 10^6$。
• 真题本质：标准的单调栈应用。从左向右扫描，用空间换时间，将寻找后继最大值的过程均摊到每次入栈出栈中。

核心算法实现

// 核心逻辑：线性扫描求右侧 NGE
for (int i = 1; i <= n; ++i) {
    while (top > 0 && a[i] > a[st[top]]) {
        ans[st[top]] = i; // 结算被弹栈元素的答案
        top--;
    }
    st[++top] = i; // 当前下标入栈
}

洛谷 P1191 矩形

• 题意简述：给出一个 $N \times N$ 的 $01$ 矩阵，求全为 $1$ 的子矩形个数。$N \le 400$。

• 真题本质：二维单调栈结合动态规划的经典计数模型。

• 解题核心：

• 悬线降维打击：预处理出 h[j] 表示当前行第 $j$ 列向上连续的 $1$ 的个数（即把每一行看作直方图的底，h 为当前直方图高度）。若 g[i][j] == 0，则 h[j] = 0。

• 动态规划破局（防重防漏）：设 dp[j] 表示在当前行中，以第 $j$ 列为右下角的全 $1$ 子矩形个数。由于每个子矩形都有且仅有一个确定的右下角，因此在右下角维度上切分集合，天然具备不重不漏的特性。

• 单调栈加速状态转移：利用单调栈寻找左侧第一个严格小于 $h[j]$ 的位置 $k$（维护严格递增栈）。

• 区间 $[k+1, j]$ 内的列：高度全部受到当前最短悬线 $h[j]$ 的制约，贡献出 $h[j] \times (j - k)$ 个新增矩形。

• 位置 $k$ 及其左侧的列：延伸能力早已被更矮的 $h[k]$ 限制，完美继承上一个合法状态 dp[k]。

• 状态转移方程： $$dp[j] = dp[k] + h[j] \times (j - k)$$

核心算法实现

// 核心逻辑：逐行更新直方图高度，利用单调栈维护局部最小值并做 DP 转移
long long total_ans = 0; // 计数问题务必开 long long

for (int i = 1; i <= n; ++i) {
    int top = 0;
    st[0] = 0; // 核心技巧：引入 0 号位置作为左边界的虚拟哨兵，h[0] = 0

    for (int j = 1; j <= n; ++j) {
        // 1. 动态更新当前行各列的直方图高度
        h[j] = (g[i][j] == 1) ? h[j] + 1 : 0;

        // 2. 维护严格单调递增栈，遇到高度 >= 的就弹栈
        while (top > 0 && h[st[top]] >= h[j]) {
            top--;
        }

        // 3. 此时 st[top] 即为左侧第一个严格矮于当前高度的位置 k
        int k = st[top];

        // 4. 状态转移并累加答案
        dp[j] = dp[k] + (long long)h[j] * (j - k);
        total_ans += dp[j];

        st[++top] = j; // 当前列下标入栈
    }
}