数据结构之单调栈：从原理到实战

1.3 核心操作解析：为什么要'弹出元素'？

大家可能会疑惑：'为什么要先弹出元素再入栈？'其实这正是单调栈的核心——为了保证栈的单调性不被破坏。

比如维护单调递增栈时，若当前元素 a[i] 比栈顶元素小，说明栈顶元素'挡路'了：如果直接入栈，栈就会出现'大元素在前、小元素在后'的情况，违背递增规则。因此需要先弹出所有 ≥ a[i] 的元素，直到栈顶元素 < a[i]（或栈为空），再将 a[i] 入栈。

举个直观的例子：假设数组 a = [5, 3, 7, 2]，维护单调递增栈的过程：

i=1，a[i]=5：栈空，直接入栈 → 栈：[5] i=2，a[i]=3：栈顶 5≥3，弹出 5；栈空，入栈 3 → 栈：[3] i=3，a[i]=7：栈顶 3＜7，直接入栈 → 栈：[3,7] i=4，a[i]=2：栈顶 7≥2，弹出 7；栈顶 3≥2，弹出 3；栈空，入栈 2 → 栈：[2]

最终栈内元素为 [2]，完美保持递增特性。

二、单调栈能解决什么问题？四大核心场景全覆盖

单调栈的核心应用场景，总结起来就是'找最近最值'——给定一个元素，找到它左侧/右侧最近的、比它大/小的元素的位置。这四类问题看似不同，实则原理相通，掌握一种就能举一反三。

先记住一句'口诀'：找左侧，正遍历；找右侧，逆遍历；比它大，单调减；比它小，单调增。这句话能帮你快速确定遍历方向和栈的单调性，下文会反复验证。

2.1 场景 1：找左侧最近的'更大元素'

问题描述

给定数组 a，对于每个元素 a[i]，找到其左侧第一个比它大的元素的下标；若不存在，返回 0。

解题思路

遍历方向：从左到右（找左侧元素，正序遍历）； 栈的单调性：维护单调递减栈（要找'更大'的元素，栈内元素从大到小，保证栈顶是最近的更大值）； 栈内存储：元素下标（最终要返回位置，存下标比存值更实用）。

代码实现

#include <iostream>
#include <stack>
using namespace std;

const int N = 3e6 + 10;
int a[N], n;
int ret[N]; // 存储每个元素的答案

void findLeftLarger() {
    stack<int> st; // 单调递减栈，存下标
    for (int i = 1; i <= n; i++) {
        // 弹出所有≤a[i]的元素，剩下的栈顶就是左侧最近的更大元素
        while (st.size() && a[st.top()] <= a[i]) {
            st.pop();
        }
        // 栈非空则栈顶是答案，否则为 0
        if (st.size()) {
            ret[i] = st.top();
        } else {
            ret[i] = 0;
        }
        st.push(i); // 入栈当前下标，维护栈的单调性
    }
    // 输出结果
    for (int i = 1; i <= n; i++) {
        cout << ret[i] << " ";
    }
    cout << endl;
}

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

测试用例验证

输入：

9 1 4 10 6 3 3 15 21 8

输出：

0 0 0 3 4 4 0 0 8

解释：

第 3 个元素 10，左侧最近的更大元素不存在 → 0； 第 4 个元素 6，左侧最近的更大元素是 10（下标 3） → 3； 第 9 个元素 8，左侧最近的更大元素是 21（下标 8） → 8。

2.2 场景 2：找左侧最近的'更小元素'

问题描述

给定数组 a，对于每个元素 a[i]，找到其左侧第一个比它小的元素的下标；若不存在，返回 0。

解题思路

遍历方向：从左到右； 栈的单调性：维护单调递增栈（要找'更小'的元素，栈内元素从小到大，栈顶是最近的更小值）； 栈内存储：元素下标。

代码实现

#include <iostream>
#include <stack>
using namespace std;

const int N = 3e6 + 10;
int a[N], n;
int ret[N];

void findLeftSmaller() {
    stack<int> st; // 单调递增栈，存下标
    for (int i = 1; i <= n; i++) {
        // 弹出所有≥a[i]的元素，剩下的栈顶就是左侧最近的更小元素
        while (st.size() && a[st.top()] >= a[i]) {
            st.pop();
        }
        ret[i] = st.size() ? st.top() : 0;
        st.push(i);
    }
    // 输出结果
    for (int i = 1; i <= n; i++) {
        cout << ret[i] << " ";
    }
    cout << endl;
}

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

测试用例验证

输入：

9 1 4 10 6 3 3 15 21 8

输出：

0 1 2 2 1 1 6 7 6

解释：

第 4 个元素 6，左侧最近的更小元素是 4（下标 2） → 2； 第 5 个元素 3，左侧最近的更小元素是 1（下标 1） → 1； 第 9 个元素 8，左侧最近的更小元素是 15（下标 6） → 6。

2.3 场景 3：找右侧最近的'更大元素'

问题描述

给定数组 a，对于每个元素 a[i]，找到其右侧第一个比它大的元素的下标；若不存在，返回 0。

解题思路

遍历方向：从右到左（找右侧元素，逆序遍历）； 栈的单调性：维护单调递减栈（找'更大'的元素，栈内递减）； 栈内存储：元素下标。

代码实现

#include <iostream>
#include <stack>
using namespace std;

const int N = 3e6 + 10;
int a[N], n;
int ret[N];

void findRightLarger() {
    stack<int> st; // 单调递减栈，存下标
    for (int i = n; i >= 1; i--) {
        // 弹出所有≤a[i]的元素，剩下的栈顶就是右侧最近的更大元素
        while (st.size() && a[st.top()] <= a[i]) {
            st.pop();
        }
        ret[i] = st.size() ? st.top() : 0;
        st.push(i);
    }
    // 输出结果
    for (int i = 1; i <= n; i++) {
        cout << ret[i] << " ";
    }
    cout << endl;
}

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

测试用例验证

输入：

9 1 4 10 6 3 3 15 21 8

输出：

2 3 7 7 7 7 8 0 0

解释：

第 1 个元素 1，右侧最近的更大元素是 4（下标 2） → 2； 第 7 个元素 15，右侧最近的更大元素是 21（下标 8） → 8； 第 8 个元素 21，右侧无更大元素 → 0。

2.4 场景 4：找右侧最近的'更小元素'

问题描述

给定数组 a，对于每个元素 a[i]，找到其右侧第一个比它小的元素的下标；若不存在，返回 0。

解题思路

遍历方向：从右到左； 栈的单调性：维护单调递增栈（找'更小'的元素，栈内递增）； 栈内存储：元素下标。

代码实现

#include <iostream>
#include <stack>
using namespace std;

const int N = 3e6 + 10;
int a[N], n;
int ret[N];

void findRightSmaller() {
    stack<int> st; // 单调递增栈，存下标
    for (int i = n; i >= 1; i--) {
        // 弹出所有≥a[i]的元素，剩下的栈顶就是右侧最近的更小元素
        while (st.size() && a[st.top()] >= a[i]) {
            st.pop();
        }
        ret[i] = st.size() ? st.top() : 0;
        st.push(i);
    }
    // 输出结果
    for (int i = 1; i <= n; i++) {
        cout << ret[i] << " ";
    }
    cout << endl;
}

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

测试用例验证

输入：

9 1 4 10 6 3 3 15 21 8

输出：

0 5 4 5 0 0 9 9 0

解释：

第 2 个元素 4，右侧最近的更小元素是 3（下标 5） → 5； 第 3 个元素 10，右侧最近的更小元素是 6（下标 4） → 4； 第 7 个元素 15，右侧最近的更小元素是 8（下标 9） → 9。

三、模板题实战：洛谷 P5788【模板】单调栈

光说不练假把式，我们以洛谷经典模板题为例，完整拆解单调栈的解题流程。

题目链接：https://www.luogu.com.cn/problem/P5788

3.1 题目描述

给出项数为 n 的整数数列 a[1...n]，定义函数 f(i) 代表数列中第 i 个元素之后第一个大于 a[i] 的元素的下标，即 f(i)=min{ j | i<j ≤n, a[j]>a[i] }。若不存在，f(i)=0。试求出 f(1...n)。

3.2 输入输出要求

• 输入：第一行正整数 n，第二行 n 个正整数 a[1...n]；
• 输出：一行 n 个整数，表示 f(1),f(2),...,f(n)；
• 数据范围：1≤n≤3×10⁶，1≤a[i]≤10⁹。

3.3 解题思路

这道题本质是'找右侧最近的更大元素'，直接套用前文的思路： 遍历方向：从右到左； 栈的单调性：单调递减栈； 栈内存储：元素下标。

3.4 完整代码实现

#include <iostream>
#include <stack>
using namespace std;

const int N = 3e6 + 10; // 适配 3e6 的大数据量
int n;
int a[N];
int ret[N]; // 存储每个元素的答案

int main() {
    ios::sync_with_stdio(false); // 关闭同步，加速输入输出
    cin.tie(0); // 解绑 cin 和 cout
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    stack<int> st; // 单调递减栈，存下标
    for (int i = n; i >= 1; i--) {
        // 弹出所有≤a[i]的元素，保证栈的单调性
        while (st.size() && a[st.top()] <= a[i]) {
            st.pop();
        }
        // 栈顶即为右侧最近的更大元素下标
        ret[i] = st.size() ? st.top() : 0;
        st.push(i); // 入栈当前下标
    }
    // 输出结果
    for (int i = 1; i <= n; i++) {
        cout << ret[i] << " ";
    }
    cout << endl;
    return 0;
}

3.5 测试用例验证

输入：

5 1 4 2 3 5

输出：

2 5 4 5 0

解释：

a[1]=1，右侧最近的更大元素是 a[2]=4 → f(1)=2； a[2]=4，右侧最近的更大元素是 a[5]=5 → f(2)=5； a[3]=2，右侧最近的更大元素是 a[4]=3 → f(3)=4； a[4]=3，右侧最近的更大元素是 a[5]=5 → f(4)=5； a[5]=5，右侧无更大元素 → f(5)=0。

四、进阶实战：单调栈的经典应用场景

除了基础的'找最近最值'，单调栈还能解决很多经典算法题，下面选取两个高频考点，带你深入理解。

4.1 实战 1：发射站（洛谷 P1901）

题目链接：https://www.luogu.com.cn/problem/P1901

题目描述

某地有 N 个能量发射站排成一行，每个发射站 i 有高度 H[i] 和能量值 V[i]，发射的能量只被两边最近的且比它高的发射站接收。求接收最多能量的发射站的能量值。

解题思路

核心需求：对每个发射站，找到左侧/右侧最近的更高发射站，将能量值累加到对应发射站； 左侧更高：正序遍历，维护单调递减栈（找更高元素）； 右侧更高：逆序遍历，维护单调递减栈； 最终遍历所有发射站的能量总和，取最大值。

完整代码

#include <iostream>
#include <stack>
using namespace std;

typedef long long LL; // 防止能量值溢出
const int N = 1e6 + 10;
int n;
LL h[N], v[N];
LL sum[N]; // 存储每个发射站接收的总能量

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i] >> v[i];
    }
    // 第一步：找左侧最近的更高发射站
    stack<int> st;
    for (int i = 1; i <= n; i++) {
        // 弹出所有≤当前高度的元素，栈顶即为左侧最近更高
        while (st.size() && h[st.top()] <= h[i]) {
            st.pop();
        }
        if (st.size()) {
            sum[st.top()] += v[i]; // 能量累加到左侧更高的发射站
        }
        st.push(i);
    }
    // 第二步：找右侧最近的更高发射站（清空栈，重新遍历）
    while (st.size()) st.pop();
    for (int i = n; i >= 1; i--) {
        while (st.size() && h[st.top()] <= h[i]) {
            st.pop();
        }
        if (st.size()) {
            sum[st.top()] += v[i]; // 能量累加到右侧更高的发射站
        }
        st.push(i);
    }
    // 第三步：找接收能量的最大值
    LL ret = 0;
    for (int i = 1; i <= n; i++) {
        ret = max(ret, sum[i]);
    }
    cout << ret << endl;
    return 0;
}

测试用例验证

输入：

3 4 2 3 5 6 10

输出：7

解释：

发射站 1（H=4，V=2）：右侧最近更高是发射站 3，能量 2 传给 3； 发射站 2（H=3，V=5）：右侧最近更高是发射站 3，能量 5 传给 3； 发射站 3（H=6，V=10）：无更高发射站，无能量接收； 总接收：发射站 3 接收 2+5=7，为最大值。

4.2 实战 2：柱状图中最大的矩形（洛谷 HISTOGRA）

题目链接：https://www.luogu.com.cn/problem/SP1805

题目描述

给定 n 个宽度为 1 的矩形的高度，求包含于这些矩形的最大子矩形面积。

解题思路

核心思路：对每个矩形 i，找到左侧/右侧最近的更矮矩形，确定该矩形能扩展的最大宽度，面积 = 高度 × 宽度； 左侧更矮：正序遍历，维护单调递增栈； 右侧更矮：逆序遍历，维护单调递增栈； 遍历所有矩形的面积，取最大值。

完整代码

#include <iostream>
#include <stack>
using namespace std;

typedef long long LL; // 防止面积溢出
const int N = 1e5 + 10;
int n;
LL h[N];
LL left_bound[N], right_bound[N]; // 左侧/右侧最近更矮矩形的下标

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin >> n, n) { // 输入 0 结束
        for (int i = 1; i <= n; i++) {
            cin >> h[i];
        }
        // 第一步：找左侧最近的更矮矩形
        stack<int> st;
        for (int i = 1; i <= n; i++) {
            while (st.size() && h[st.top()] >= h[i]) {
                st.pop();
            }
            left_bound[i] = st.size() ? st.top() : 0;
            st.push(i);
        }
        // 第二步：找右侧最近的更矮矩形
        while (st.size()) st.pop();
        for (int i = n; i >= 1; i--) {
            while (st.size() && h[st.top()] >= h[i]) {
                st.pop();
            }
            right_bound[i] = st.size() ? st.top() : n + 1;
            st.push(i);
        }
        // 第三步：计算最大面积
        LL ret = 0;
        for (int i = 1; i <= n; i++) {
            LL width = right_bound[i] - left_bound[i] - 1;
            ret = max(ret, h[i] * width);
        }
        cout << ret << endl;
    }
    return 0;
}

测试用例验证

输入：

7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0

输出：

8 4000

解释：

第一组数据：最大矩形是高度为 3、宽度为 2（下标 6-7），或高度为 4、宽度为 2（下标 3-4），面积 8； 第二组数据：4 个高度 1000 的矩形，宽度 4，面积 1000×4=4000。

五、单调栈的核心总结与避坑指南

5.1 核心总结

单调性选择：找'更大'元素 → 维护单调递减栈；找'更小'元素 → 维护单调递增栈； 遍历方向：找左侧元素 → 正序遍历；找右侧元素 → 逆序遍历； 栈内存储：优先存下标（需返回位置时直接用，存值无法对应位置）； 时间复杂度：每个元素入栈/出栈各一次，O(n)，适配大数据量（如 3e6）。

5.2 避坑指南

数据范围：注意 int 和 long long 的选择，避免溢出（如面积、能量值计算）； 输入输出优化：大数据量下需加 ios::sync_with_stdio(false); cin.tie(0);，否则会超时； 栈的清空：多次使用栈时，需先清空（while(st.size()) st.pop();）； 边界处理：无对应元素时返回 0（或 n+1），需提前定义好边界值。

总结

单调栈看似简单，实则是'贪心思想'与'栈结构'的完美结合。它的核心价值在于将嵌套循环的暴力解法，优化为线性时间复杂度，这也是算法优化的核心思路——用空间换时间，用数据结构约束逻辑。

掌握单调栈，不仅能解决'找最近最值'类问题，更能理解'如何通过维护数据结构的特性来简化问题'。建议大家结合本文的例题，手动模拟栈的入栈、出栈过程，真正吃透每一步操作的意义。相信通过反复练习，你也能熟练运用单调栈，轻松应对算法面试和竞赛中的相关问题！