单调栈——让数据保持单调有序的利器

你有没有在学校排队时，想找到前面第一个比自己高的人？或者打游戏时，想知道往后第一个更厉害的怪物？这些问题都可以用一种叫“单调栈”的数据结构快速解决。它的关键就是让栈里的元素始终保持“单调”——要么一直变大，要么一直变小。这样就能在很短的时间内找出每个元素的“下一个更大”或“下一个更小”的答案。

生活中的例子：排队买奶茶

假设你和同学们排队买奶茶，你想知道每个人的右边第一个比自己高的人是谁（身高从低到高排队）。你可以一个个往后看，但这样太慢了。想象一下：你站在队伍最前面，后面的人依次走过来。如果你发现后面有一个人比你矮，那他/她完全不可能挡住你——因为他/她比你矮，你一眼就能看到更后面的人。所以，只有比你高的人才值得注意。我们可以用一个“魔法栈”来记住那些还没找到更高人的人，只要新来的人比栈顶的人高，栈顶的人就找到了答案。这样每个人最多进栈出栈一次，非常高效。

另外，山峰的例子也很贴切：你站在一排连绵的山峰前，想知道每座山峰右边第一座比自己高的山峰是哪一座。用单调栈，只需要从左往右走一趟就知道答案。

什么是单调栈？

单调栈（Monotonic Stack）本质上还是一个普通的栈（后进先出），但是多了个规矩：每次要往栈里放新数据时，先把栈里那些破坏“单调性”的旧数据弹出，然后再放进去。这样，栈里的数据从底到顶始终保持单调递增或递减。

常见的两种单调栈：

类型	栈底到栈顶的变化	用途举例
单调递增栈	越来越小（栈顶最小）	找“下一个更小元素”或“左边更大元素”
单调递减栈	越来越大（栈顶最大）	找“下一个更大元素”或“左边更小元素”

怎么记呢？以“单调递减栈”为例：栈里元素从底到顶是递减的，也就是栈顶是最小的。当遇到一个更大的新元素时，就会把栈里那些比它小的元素弹出来，这些被弹出的元素的下一个更大就是当前元素。

核心思想：一边弹栈，一边记答案

我们用“下一个更大元素”来详细讲解。给你一个数组 nums = [2, 1, 3, 4, 2]，对每个位置，找到它右边第一个比它大的数，没有就填 -1。答案应该是 [3, 3, 4, -1, -1]。

操作过程：

从左往右遍历数组。
维护一个单调递减栈（栈里存下标，栈底到栈顶对应数值递减，即栈顶最小）。
对于当前位置 i，只要栈不空，并且 nums[i] 大于栈顶对应的数，那就说明栈顶元素找到了下一个更大值——就是 nums[i]。弹出栈顶，记下答案，重复直到条件不成立。
把当前下标 i 压入栈。

用ASCII图走一遍：

原始数组：  2   1   3   4   2
下标：      0   1   2   3   4

初始栈空
i=0, nums=2 → 栈空，直接压入0
  栈底[0]栈顶
i=1, nums=1 → 1 < 2（栈顶值），不破坏递减，压入1
  栈[0,1]  (值2,1)
i=2, nums=3 → 3 > 1，弹出1，记录ans[1]=3
               3 > 2，弹出0，记录ans[0]=3
               栈空，压入2
  栈[2] (值3)
i=3, nums=4 → 4 > 3，弹出2，记录ans[2]=4
               栈空，压入3
  栈[3] (值4)
i=4, nums=2 → 2 < 4，压入4
  栈[3,4] (值4,2)
遍历结束，栈里剩下的[3,4]没找到更大值，结果保持-1
最终ans = [3, 3, 4, -1, -1]

核心思想：每个元素入栈一次，出栈一次，所以总时间就是 O(n)。并且每次弹出的时候，答案就确定了——被弹出元素的下一个更大元素就是当前元素。

常见错误（新手容易掉坑）

比较符号搞反：要找“下一个更大”应该用 >，找“下一个更小”应该用 <。如果写反了，结果会全错。
存的是值还是下标：通常存下标更灵活，因为我们可以通过下标访问到原值，还能计算距离（比如“几天后升温”）。如果只存值，就丢失了位置信息。
忘记处理栈里剩余的元素：遍历结束后，栈里剩下的元素在右边没有更大（或更小）的元素，结果应该填 -1 或特殊值。可以在初始化时就把答案全设为 -1，这样就不需要额外处理了。
栈空检查：在 while 循环里必须先判断 !st.empty()，否则直接访问 st.top() 会崩溃。

完整可运行代码（C++ 和 Python）

C++ 完整代码（包含测试）

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

// 函数：返回数组中每个元素的下一个更大元素
// 如果不存在，对应位置为 -1
vector<int> nextGreaterElement(const vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);    // 结果数组，先全填 -1
    stack<int> st;                // 存储下标的栈，栈底到栈顶递减

    for (int i = 0; i < n; ++i) {
        // 当前元素 nums[i] 不断弹出比它小的栈顶元素
        while (!st.empty() && nums[i] > nums[st.top()]) {
            int idx = st.top();   // 取栈顶下标
            st.pop();             // 弹出它
            result[idx] = nums[i]; // 当前元素就是它的下一个更大
        }
        // 把当前下标入栈
        st.push(i);
    }
    // 栈中剩余元素没有右更大，result 早已设为 -1
    return result;
}

// 辅助打印
void printVector(const vector<int>& vec) {
    cout << "[";
    for (size_t i = 0; i < vec.size(); ++i) {
        cout << vec[i];
        if (i != vec.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

int main() {
    vector<int> nums = {2, 1, 3, 4, 2};
    vector<int> res = nextGreaterElement(nums);
    cout << "原数组: ";
    printVector(nums);
    cout << "下一个更大元素: ";
    printVector(res);  // 输出 [3, 3, 4, -1, -1]

    // 再试一个例子：考试分数，找右边第一个更高的分数
    vector<int> scores = {80, 95, 70, 88, 100};
    vector<int> highScores = nextGreaterElement(scores);
    cout << "考试分数: ";
    printVector(scores);
    cout << "第一个更高分: ";
    printVector(highScores); // 输出 [95, 100, 88, 100, -1]
    return 0;
}

Python 完整代码（包含测试）

def next_greater_element(nums):
    """返回数组中每个元素的下一个更大元素列表"""
    n = len(nums)
    result = [-1] * n          # 结果列表，初始 -1
    stack = []                 # 单调递减栈，存下标

    for i in range(n):
        # 只要栈非空且当前元素大于栈顶对应值
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()      # 弹出栈顶下标
            result[idx] = nums[i]  # 当前元素就是答案
        stack.append(i)            # 当前下标入栈

    return result

# 测试
nums = [2, 1, 3, 4, 2]
res = next_greater_element(nums)
print("原数组:", nums)
print("下一个更大元素:", res)  # [3, 3, 4, -1, -1]

# 另一个例子：零花钱数，找右边第一笔更多的零花钱
allowance = [5, 10, 3, 8, 12]
ans = next_greater_element(allowance)
print("零花钱:", allowance)
print("下一笔更多的:", ans)  # [10, 12, 8, 12, -1]

代码解释（以C++为例）：

stack<int> st：存放数组下标，栈内保持递减（即栈顶对应的值最小）。
在 while 循环里，我们用 nums[i] > nums[st.top()] 判断是否弹栈。一旦成立，说明栈顶元素找到了它的下一个更大元素。
弹出栈顶后，把 nums[i] 赋给 result[idx]。
注意：result 初始化全为 -1，栈里剩下的元素无需再修改。
整个数组遍历一遍，时间 O(n)，空间 O(n)。

变体：找下一个更小元素

只需要把比较符号换成 <，并维护单调递增栈（栈顶最大）。代码几乎一样：

vector<int> nextSmallerElement(const vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    stack<int> st;  // 单调递增栈（栈底到栈顶递增，栈顶最大）
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && nums[i] < nums[st.top()]) {
            result[st.top()] = nums[i];
            st.pop();
        }
        st.push(i);
    }
    return result;
}

单调栈的应用场景（不只一个）

除了找下一个更大/更小，单调栈还能解决很多经典题目：

问题	怎么做
每日温度（LeetCode 739）	找右边第一个更高温度的距离，本质就是“下一个更大元素”的距离
接雨水（LeetCode 42）	用单调递减栈计算每个凹槽能接多少水
柱状图中最大矩形（LeetCode 84）	找每个柱子左边和右边第一个比它矮的柱子，用单调递增栈
滑动窗口最大值（LeetCode 239）	可以用单调递减队列（双端队列），思想类似

很多比赛中的“左边第一个大”、“右边第一个小”都可以用单调栈轻松解决。

总结要点

单调栈 = 栈 + 单调性。入栈前先把破坏单调的元素弹出，保证栈内始终单调。
通常存下标，方便同时得到值和位置。
注意比较方向和栈的单调类型对应：找更大用递减栈，找更小用递增栈。
每个元素入栈出栈各一次，时间复杂度 O(n)，非常高效。
初学者可以先拿纸笔手动模拟一遍数组，特别体会“弹出时确定答案”这个时刻。

如果你已经掌握了栈的基本操作（push、pop、top），那么单调栈就是它的一个实用升级。建议去练几道经典题，比如“下一个更大元素 I”、"每日温度"，很快就能熟练掌握。

相关指引：想打好基础，可以先学习普通栈的用法（后进先出）。之后可以尝试用单调队列解决“滑动窗口最大值”，两者的思想很像。如果你对动态规划感兴趣，也可以看看“接雨水”的多种解法，其中单调栈是最优雅的一种。

例题精讲