单调栈：原理、图解与 C++ 实战

一、什么是单调栈

单调栈（Monotone Stack）是一种特殊的栈结构，它在普通栈"后进先出（LIFO）"的基础上，额外要求栈内元素保持单调性（单调递增或单调递减）。

它的典型应用场景是：在一组数据中，对每个元素找"下一个比它大/小的元素"。这类问题如果用暴力双层循环是 O(n²)，用单调栈可以降到 O(n)。

1.1 两种单调栈

二、核心原理与图解

理解单调栈的关键，是理解"弹栈的瞬间发生了什么"。当一个新元素入栈时，它会"击落"所有比它弱（破坏单调性）的栈顶元素——被击落的元素，它们的"下一个更大/小元素"恰好就是这个新元素。

2.1 一个完整的例子

以数组 [2, 1, 2, 4, 3] 为例，求每个元素右边第一个比它大的元素。我们用单调递减栈（栈内从底到顶递减），栈中存的是元素下标。

2.2 复杂度分析

三、通用模板

掌握下面这个模板，90% 的单调栈题目都能套用：

// 单调栈通用模板：求每个元素右边第一个更大元素的下标
// 若不存在返回 -1
vector<int> nextGreaterElement(const vector<int>& nums) {
    int n = nums.size();
    vector<int> ans(n, -1);
    stack<int> st;  // 存下标，栈内对应值从底到顶递减

    for (int i = 0; i < n; ++i) {
        // 当前值比栈顶值大，栈顶找到了"下一个更大"
        while (!st.empty() && nums[st.top()] < nums[i]) {
            ans[st.top()] = i;   // 或填 nums[i]，看题目要求
            st.pop();
        }
        st.push(i);
    }
    return ans;
}

四、示例一：每日温度

题目（LeetCode 739）：给定一个数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i] 是第 i 天之后第一个更暖和的天数距离第 i 天的天数。如果没有更暖和的一天，填 0。

4.1 示例

输入：[73, 74, 75, 71, 69, 72, 76, 73]
输出：[1, 1, 4, 2, 1, 1, 0, 0]

4.2 C++ 代码

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

vector<int> dailyTemperatures(const vector<int>& T) {
    int n = T.size();
    vector<int> ans(n, 0);
    stack<int> st;  // 存下标，栈内温度从底到顶递减

    for (int i = 0; i < n; ++i) {
        // 当前温度比栈顶那天的温度高，栈顶那天找到了"更暖和的一天"
        while (!st.empty() && T[st.top()] < T[i]) {
            int prevDay = st.top();
            ans[prevDay] = i - prevDay;  // 距离 = 当前下标 - 之前下标
            st.pop();
        }
        st.push(i);
    }
    return ans;
}

这个例子和通用模板几乎一样，唯一区别是 ans 存的是"距离天数"而非下标，所以多了一步 i - prevDay。

五、示例二：下一个更大元素 II（环形数组）

题目（LeetCode 503）：给定一个循环数组 nums（最后一个元素的下一个是第一个），返回每个元素的下一个更大元素，如果不存在填 -1。

5.1 思路：环形展开为线性

处理环形数组的常用技巧是"拉长两倍"——把数组复制一份接在后面，遍历 [0, 2n)，用模运算访问原数组。这样每个元素都有机会"绕一圈"找到自己的下一个更大元素。

5.2 C++ 代码

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

vector<int> nextGreaterElements(const vector<int>& nums) {
    int n = nums.size();
    vector<int> ans(n, -1);
    stack<int> st;

    // 关键：遍历 2n 次，用 i%n 取真实下标
    for (int i = 0; i < 2 * n; ++i) {
        int idx = i % n;
        while (!st.empty() && nums[st.top()] < nums[idx]) {
            ans[st.top()] = nums[idx];
            st.pop();
        }
        // 只在前 n 次入栈，避免重复入栈
        if (i < n) st.push(idx);
    }
    return ans;
}

六、示例三：柱状图中最大的矩形

题目（LeetCode 84）：给定 n 个非负整数，表示柱状图中各柱子的高度，每根柱子宽度为 1，求能组成的最大矩形面积。

6.1 问题分析

最大矩形一定"以某根柱子高度为高，向左右扩展到第一个比它矮的柱子为止"。所以问题转化为：对每根柱子，找左右两边第一个比它矮的位置——典型的单调栈问题。

6.2 C++ 代码

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

int largestRectangleArea(const vector<int>& heights) {
    int n = heights.size();
    stack<int> st;  // 单调递增栈（栈内高度从底到顶递增）
    int maxArea = 0;

    // 在末尾加一个虚拟高度 0，强制把栈里所有柱子弹出收尾
    for (int i = 0; i <= n; ++i) {
        int h = (i == n) ? 0 : heights[i];  // 哨兵
        while (!st.empty() && heights[st.top()] > h) {
            int height = heights[st.top()];
            st.pop();
            // 左边界：栈顶下面的那个，若栈空则左边界为 -1
            int left = st.empty() ? -1 : st.top();
            int width = i - left - 1;
            maxArea = max(maxArea, height * width);
        }
        st.push(i);
    }
    return maxArea;
}

七、总结与适用场景

典型题目清单

• LeetCode 496：下一个更大元素 I（基础）
• LeetCode 503：下一个更大元素 II（环形）
• LeetCode 739：每日温度（基础）
• LeetCode 84：柱状图中最大的矩形（进阶）
• LeetCode 85：最大矩形（二维扩展）
• LeetCode 42：接雨水（双指针/单调栈均可）
• LeetCode 402：移掉 K 位数字（结合贪心）
• LeetCode 316：去除重复字母（结合贪心 + 计数）