单调栈入门：从“右边第一个更大的数”讲起

Table of contents

先认识“栈”

栈（stack）是一种只能从一头放、从同一头拿的容器。最好的类比是一摞盘子：

• 洗好的盘子只能放在最上面；
• 要用盘子，也只能从最上面拿。

所以最后放上去的，最先被拿走，这叫“后进先出”。最上面那个位置叫“栈顶”，最下面叫“栈底”。

在 Python 里，一个普通的 list 就能当栈用，只需要三个操作：

stack: list[int] = []

stack.append(3)  # 放一个到栈顶：[3]
stack.append(1)  # 再放一个：[3, 1]，栈顶是 1
top = stack[-1]  # 看一眼栈顶，不拿走：1
stack.pop()  # 拿走栈顶：[3]

写成文字时，本文统一把栈画成从左到右的一排，左边是栈底，右边是栈顶，比如 [3, 1] 表示 3 在下面、1 在上面。

“单调栈”是什么

单调栈就是栈里的元素从栈底到栈顶始终保持单调（一直变小，或者一直变大）的栈。

• 从栈底到栈顶一直变小，叫单调递减栈，比如 [9, 6, 4, 1]；
• 从栈底到栈顶一直变大，叫单调递增栈，比如 [1, 4, 6, 9]。

光看定义很难理解它有什么用。单调栈不是凭空设计出来的，而是在解决一类问题时自然出现的。下面就从这个问题讲起。

从一个问题开始：右边第一个更大的数

给一个整数数组，对每个元素，找出它右边第一个比它大的元素。找不到就记为 -1。

例子：nums = [3, 1, 2, 5, 4]

答案是 [5, 2, 5, -1, -1]。

暴力做法

就照上面表格的方式：对每个元素，往右一个一个找。

def next_greater_brute_force(nums: list[int]) -> list[int]:
    answer = [-1] * len(nums)
    for i, num in enumerate(nums):
        for later in nums[i + 1 :]:
            if later > num:
                answer[i] = later
                break
    return answer

最坏情况下（比如数组一直递减，谁都找不到答案），每个元素都要扫到底，时间复杂度 O(n²)。

慢的原因是：同一段元素被反复扫描。处理下标 0 时已经看过了 1、2、5，处理下标 1 时又从头看一遍。

换个方向：让元素“进场”，看谁能拿到答案

暴力做法是“每个元素主动往右找答案”。换个角度：让元素从左到右一个一个进场，每进来一个，看它能成为谁的答案。

把每个数想象成一个人，数值就是他的身高。每个人都想知道：“我右边第一个比我高的人是谁？”

• 人从左到右一个一个走进房间。
• 房间里有一块“等待区”，还没找到答案的人都站在这里。
• 每进来一个新人，等待区里比他矮的人就等到了答案，答案就是这个新人，于是他们离开等待区。
• 然后新人自己也站进等待区，等更高的人出现。
• 所有人都进场后，还留在等待区的人，右边没有比他高的，答案是 -1。

一步一步走一遍

还是 nums = [3, 1, 2, 5, 4]。等待区按进来的先后从左往右排。

第 1 步：3 进场

• 等待区是空的，没人能拿到答案。
• 3 站进等待区。
• 等待区：[3]

第 2 步：1 进场

• 等待区里最后进来的是 3。1 比 3 矮，3 拿不到答案。
• 1 站进等待区。
• 等待区：[3, 1]

第 3 步：2 进场

• 先看最后进来的 1：2 比 1 高，1 的答案是 2，1 离开。
• 再看 3：2 比 3 矮，3 拿不到答案，停下。
• 2 站进等待区。
• 等待区：[3, 2]

第 4 步：5 进场

• 看最后进来的 2：5 比 2 高，2 的答案是 5，2 离开。
• 再看 3：5 比 3 高，3 的答案是 5，3 离开。
• 等待区空了，停下。
• 5 站进等待区。
• 等待区：[5]

第 5 步：4 进场

• 看 5：4 比 5 矮，5 拿不到答案，停下。
• 4 站进等待区。
• 等待区：[5, 4]

全部进场后：等待区里剩下 5 和 4，它们的答案都是 -1。

汇总成一张表：

答案：3→5、1→2、2→5、5→-1、4→-1，也就是 [5, 2, 5, -1, -1]，和暴力做法一样。

关键发现：等待区一定是从左到右递减的

看最后一列：[3]、[3, 1]、[3, 2]、[5]、[5, 4]，每一个都是从左到右越来越矮。这不是巧合，而是必然：

假设等待区里有一个矮个子 A 站在高个子 B 的左边（A 先进来，B 后进来，A 比 B 矮）。那么 B 进场的那一刻，A 就应该拿到答案离开了。所以这种情况不可能存在。

既然等待区一定是递减的，就能得到两个很实用的结论：

1. 新人进场时，从最后进来的人开始往前检查就行。 遇到第一个不比新人矮的人，就可以停下了，因为再往前的人只会更高，同样拿不到答案。
2. 每次离开的、新加入的，都在等待区的同一头（最右边）。 这正是栈的“后进先出”。

这个永远递减的等待区，就是单调递减栈。 它不是被刻意设计成递减的，而是“没找到答案的人留下来”这条规则自然导致的。

写成代码

实际写代码时，栈里存的通常是下标而不是值。因为拿到答案时，我们要知道是哪个位置的答案，存下标既能找回值（nums[i]），又能填对位置。

def next_greater(nums: list[int]) -> list[int]:
    answer = [-1] * len(nums)
    waiting: list[int] = []  # 还没找到答案的下标，对应的值从栈底到栈顶递减

    for i, num in enumerate(nums):
        # 新元素比栈顶大：栈顶等到了答案
        while waiting and num > nums[waiting[-1]]:
            answer[waiting.pop()] = num
        waiting.append(i)

    return answer

这里特意把栈命名为 waiting，强调它的含义：还在等答案的元素。循环结束后还在栈里的元素不用处理，因为 answer 一开始就填好了 -1。

对照上面的步骤看代码：

• while 循环就是“从最后进来的人开始往前检查，比新人矮的拿到答案离开”；
• waiting.append(i) 就是“新人站进等待区”。

为什么是 O(n)

代码里有两层循环，看起来像 O(n²)，其实不是。换个角度数：每个下标最多进栈一次、出栈一次。while 循环每执行一次就有一个元素出栈，整个过程加起来最多出栈 n 次。所以总的时间复杂度是 O(n)，空间复杂度也是 O(n)（最坏情况下所有元素都在栈里，比如数组一直递减）。

一个变化：要的是“距离”而不是“值”

很多题目问的不是“右边第一个更大的数是多少”，而是“要往右走几步才能遇到它”。比如：给你每天的气温，问每一天要再等几天才会变暖。

这时栈里存下标的好处就体现出来了：拿到答案时，用当前下标减去栈顶下标，就是距离。

def days_until_warmer(temperatures: list[int]) -> list[int]:
    answer = [0] * len(temperatures)
    waiting: list[int] = []  # 还没等到更暖一天的日期

    for today, temperature in enumerate(temperatures):
        while waiting and temperature > temperatures[waiting[-1]]:
            day = waiting.pop()
            answer[day] = today - day
        waiting.append(today)

    return answer

days_until_warmer([3, 1, 2, 5, 4]) 的结果是 [3, 1, 1, 0, 0]：第 0 天要等 3 天（到第 3 天的 5 度），第 1 天等 1 天，以此类推；等不到的记为 0。

这正是 Hot 100 里的 739. 每日温度。

一个附赠：入栈时的栈顶，是“左边第一个不比它小的”

单调栈还有一个容易被忽略的性质。新元素在弹完比它小的元素、准备入栈时，此刻的栈顶，就是它左边第一个大于或等于它的元素。

还是看上面的步骤：

• 2 进场，弹走 1 之后栈顶是 3，所以 2 左边第一个不比它小的是 3；
• 4 进场，什么都没弹，栈顶是 5，所以 4 左边第一个不比它小的是 5。

原因和前面一样：比它小的都被弹走了，剩下的栈顶就是离它最近的、不比它小的那个。

def previous_greater_or_equal(nums: list[int]) -> list[int]:
    answer = [-1] * len(nums)
    stack: list[int] = []

    for i, num in enumerate(nums):
        while stack and num > nums[stack[-1]]:
            stack.pop()
        if stack:
            answer[i] = nums[stack[-1]]
        stack.append(i)

    return answer

previous_greater_or_equal([3, 1, 2, 5, 4]) 的结果是 [-1, 3, 3, -1, 5]。

也就是说，一次扫描能同时得到两样东西：一个元素出栈时，让它出栈的新元素是它“右边第一个更大的”，出栈后的新栈顶是它“左边第一个不比它小的”。接雨水的单调栈解法用的正是这一点：左右两个“更高的”元素，就是一个坑的左墙和右墙。

模板和变体

把上面的代码抽象一下，单调栈的骨架只有几行（这是伪代码，应该弹出、处理 要按题目替换）：

stack = []
for i, num in enumerate(nums):
    while stack 不空 and 应该弹出(nums[stack[-1]], num):
        top = stack.pop()
        处理 top：num 是 top 右边第一个满足条件的元素
    处理 i：如果 stack 不空，stack[-1] 是 i 左边第一个不满足弹出条件的元素
    stack.append(i)

改一改弹出条件，就能找不同的东西：

记忆方法：要找更大的，就让小的被弹走，栈里自然留下递减的序列；要找更小的，反过来。

什么时候该想到单调栈

题目里出现这些说法时，就可以考虑单调栈：

• “下一个更大 / 更小的元素”；
• “左边 / 右边第一个比它大 / 小的”；
• “还要等几天 / 几步才能……”；
• 需要找到“被两边更高（或更矮）的元素夹住”的区间，比如接雨水、柱状图里的最大矩形。

Hot 100 里用到单调栈的题：

容易踩的坑

1. 栈里存值还是存下标：大多数题目要存下标。存下标能找回值，也能算距离、填答案；只存值的话，这些信息就丢了。
2. 严格比较还是非严格比较：> 和 >= 决定了相等的元素会不会互相弹出，结果可能不同。写之前想清楚“相等算不算更大”。
3. 忘了处理循环结束后栈里剩下的元素：它们是“到最后都没等到答案”的元素。本文的写法是一开始就把答案初始化成 -1 或 0，所以不用额外处理；如果题目对它们有特殊要求，记得在循环后单独处理。
4. 担心复杂度是 O(n²)：别被两层循环吓到，按“每个元素最多进出栈各一次”来数，是 O(n)。

一句话总结

单调栈就是一个“还在等答案的人”的等待区。 新元素进来时，把比它小（或大）的都结算掉，剩下的自然保持单调。它能在 O(n) 时间内，为每个元素找到左边或右边第一个更大（或更小）的元素。

附：完整测试代码

把文中的三个函数和对应的暴力解法放在一起，做 3000 组随机对拍：

"""对拍测试：以暴力解法为基准，验证单调栈的几种写法。"""

import random
from collections.abc import Callable


def next_greater_brute_force(nums: list[int]) -> list[int]:
    answer = [-1] * len(nums)
    for i, num in enumerate(nums):
        for later in nums[i + 1 :]:
            if later > num:
                answer[i] = later
                break
    return answer


def next_greater(nums: list[int]) -> list[int]:
    answer = [-1] * len(nums)
    waiting: list[int] = []

    for i, num in enumerate(nums):
        while waiting and num > nums[waiting[-1]]:
            answer[waiting.pop()] = num
        waiting.append(i)

    return answer


def days_until_warmer(temperatures: list[int]) -> list[int]:
    answer = [0] * len(temperatures)
    waiting: list[int] = []

    for today, temperature in enumerate(temperatures):
        while waiting and temperature > temperatures[waiting[-1]]:
            day = waiting.pop()
            answer[day] = today - day
        waiting.append(today)

    return answer


def previous_greater_or_equal(nums: list[int]) -> list[int]:
    answer = [-1] * len(nums)
    stack: list[int] = []

    for i, num in enumerate(nums):
        while stack and num > nums[stack[-1]]:
            stack.pop()
        if stack:
            answer[i] = nums[stack[-1]]
        stack.append(i)

    return answer


def days_until_warmer_brute_force(temperatures: list[int]) -> list[int]:
    answer = [0] * len(temperatures)
    for day, temperature in enumerate(temperatures):
        for later in range(day + 1, len(temperatures)):
            if temperatures[later] > temperature:
                answer[day] = later - day
                break
    return answer


def previous_greater_or_equal_brute_force(nums: list[int]) -> list[int]:
    answer = [-1] * len(nums)
    for i, num in enumerate(nums):
        for earlier in reversed(nums[:i]):
            if earlier >= num:
                answer[i] = earlier
                break
    return answer


Scan = Callable[[list[int]], list[int]]

# (单调栈写法, 对应的暴力写法)
PAIRS: list[tuple[Scan, Scan]] = [
    (next_greater, next_greater_brute_force),
    (days_until_warmer, days_until_warmer_brute_force),
    (previous_greater_or_equal, previous_greater_or_equal_brute_force),
]


def check_fixed_cases() -> None:
    assert next_greater([3, 1, 2, 5, 4]) == [5, 2, 5, -1, -1]
    assert next_greater([]) == []
    assert days_until_warmer([3, 1, 2, 5, 4]) == [3, 1, 1, 0, 0]
    assert previous_greater_or_equal([3, 1, 2, 5, 4]) == [-1, 3, 3, -1, 5]


def check_random_cases(rounds: int = 3000, seed: int = 0) -> None:
    rng = random.Random(seed)
    for _ in range(rounds):
        nums = [rng.randint(0, 6) for _ in range(rng.randint(0, 20))]
        for fast, slow in PAIRS:
            assert fast(nums) == slow(nums), f"{fast.__name__}({nums})"


def main() -> None:
    check_fixed_cases()
    check_random_cases()
    print("all passed")


if __name__ == "__main__":
    main()