---

算法专题：单调栈 (Monotonic Stack)

一、 定义与核心思想

1. 什么是单调栈？

单调栈是一种特殊的栈结构，它在元素入栈的过程中，始终保持栈内元素（或元素对应的值）是单调递增或单调递减的。

• 单调递增栈： 从栈底到栈顶，元素是递增的。
• 单调递减栈： 从栈底到栈顶，元素是递减的。

2. 单调栈的应用场景

单调栈的核心作用是高效地找到数列中元素 左边或右边第一个比它大/小的元素 的位置。

• 问题示例： 寻找“下一个更大元素”（Next Greater Element）。

3. 为什么使用单调栈？（时间复杂度分析）

对于寻找“下一个更大元素”这类问题，暴力解法的时间复杂度是 $O(N^2)$（每个元素都要向后遍历）。

单调栈的优势在于：它确保了每个元素最多只会被压入栈一次和弹出栈一次。因此，整个算法的运行时间是线性的，时间复杂度为 $\mathbf{O(N)}$，效率极高。

---

二、 算法原理详解：以寻找“下一个更大元素”为例

我们以寻找**“下一个更大元素”为例，来构建一个单调递减栈**。

目标： 对于数列 $A$ 中的每个元素 $A[i]$，找到它右边第一个比它大的元素 $A[j]$ 的下标 $j$。

1. 栈内存储什么？

为了方便记录结果，栈中存储的是元素的下标 $i$，而不是元素的值 $A[i]$。

2. 栈的维护（单调递减栈的构建）

假设当前遍历到元素 $A[i]$：

步骤	栈顶元素 $A[\text{top}]$ vs. 当前元素 $A[i]$	操作	含义
Step 1: 判定	$\mathbf{A[\text{top}] < A[i]}$	出栈并记录	$A[i]$ 是 $A[\text{top}]$ 一直在等待的“下一个更大元素”。记录结果，并弹出 $A[\text{top}]$。重复此步骤直到不满足条件。
Step 2: 入栈	循环结束后	入栈	将当前元素 $i$ 压入栈。它将作为之后元素的潜在“下一个更大元素”。

3. 栈的意义

在遍历到 $A[i]$ 时，栈中剩下的元素 $A[k]$ ($k<i$) 都满足 $A[k] \ge A[i]$。它们是暂时没找到右侧更大元素的“候选者”，并且它们的值从栈底到栈顶是递减的。

---

三、 C++ 代码实现示例

以下代码实现了寻找数列中每个元素的“下一个更大元素”的下标。

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

using namespace std;

/**
 * 求解 Next Greater Element (NGE) 的下标
 * * @param a 输入的数列
 * @param n 数列长度
 * @return f 数组，f[i] 存储 a[i] 右边第一个更大元素的下标 (1-based)，
 * 若不存在则为 0。
 */
vector<int> find_nge_index(const vector<int>& a, int n) {
    
    // f 数组用于存储结果，初始化为 0。
    // 注意：输入数组 a 是 0-based，但 f 数组大小设置为 n+1 方便使用 1-based 下标
    vector<int> f(n + 1, 0); 
    
    // stak 存储元素的【下标】，维护一个单调递减序列。
    stack<int> stak; 

    // 遍历数列（使用 1-based 模拟，下标 i 从 1 到 n）
    for (int i = 1; i <= n; ++i) {
        
        // 获取当前元素的值（注意数组 a 是 0-based，需要访问 a[i-1]）
        int current_value = a[i - 1]; 

        // 核心循环：如果栈不为空 且 栈顶元素的值 < 当前值
        // 说明 current_value 是栈顶元素等待的 NGE
        while (!stak.empty()) {
            
            // 获取栈顶元素的下标
            int top_index = stak.top(); 
            // 获取栈顶元素的值
            int top_value = a[top_index - 1]; 

            if (top_value < current_value) {
                // 找到了：记录结果
                f[top_index] = i; 
                // 栈顶元素任务完成，出栈
                stak.pop(); 
            } else {
                // 栈顶元素 >= 当前元素，单调性保持，停止弹出
                break; 
            }
        }

        // 将当前元素的【下标 i】入栈，等待右边更大的元素出现
        stak.push(i);
    }

    // 循环结束后，栈中剩下的元素 f[k] 仍然保持为 0，表示右侧没有更大的元素。
    
    return f;
}

int main() {
    
    // 示例输入：
    // 下标:   1  2  3  4  5  6  7
    // 数值:   5  3  4  7  2  6  1
    vector<int> a = {5, 3, 4, 7, 2, 6, 1};
    int n = a.size();

    vector<int> f = find_nge_index(a, n);

    cout << "原始数列 (1-based):" << endl;
    for (int i = 0; i < n; ++i) {
        cout << a[i] << " ";
    }
    cout << "\n----------------------" << endl;
    
    cout << "NGE 下标 (f[i]):" << endl;
    // f 数组是 1-based，从 f[1] 到 f[n]
    for (int i = 1; i <= n; ++i) {
        // 输出 f[i] 的值
        cout << f[i] << " "; 
    }
    cout << endl;
    
    // 预期输出：
    // 5 -> 4 (下标 4)
    // 3 -> 4 (下标 4)
    // 4 -> 4 (下标 4)
    // 7 -> 0 (不存在)
    // 2 -> 6 (下标 6)
    // 6 -> 0 (不存在)
    // 1 -> 0 (不存在)
    // 结果：4 4 4 0 6 0 0
    
    return 0;
}

---

四、 思考与拓展

1. 单调递增栈： 如果要找左边第一个比它大或右边第一个比它小的元素，应该如何调整栈的单调性和遍历方向？（提示：寻找“左边”通常只需要改变遍历方向，寻找“更小”则需要使用单调递增栈。）
2. 实际应用： 单调栈是计算“柱状图中最大的矩形”面积问题（LeetCode 84）的核心算法。