单调栈：下一个更大元素

状态：待补充。核心模板与一阶直觉已就位；「柱状图中最大矩形」「环形数组」两节尚未写完，先占位。

1. 问题描述

给定数组，对每个元素问：右边第一个比它大的元素在哪（值或下标）？暴力是每个位置向后扫，最坏 $O(n^2)$。单调栈把全体元素的等待与回答组织成一次 $O(n)$ 的遍历。

2. 直觉：等待队列

从左往右扫描。维护一个栈，栈里存还没有等到答案的元素——并且它们从栈底到栈顶单调递减：

• 新来的元素 x 比栈顶大？那栈顶的答案就是 x——弹栈、记录答案；重复直到栈顶不小于 x，再把 x 入栈；
• x 更小？它入栈，继续等待。

为什么弹栈是安全的？被弹出的元素此刻拿到了答案，之后再也不需要它——每个元素至多入栈、出栈各一次，总代价 $O(n)$。这是「用摊还换直觉」的典型结构。

3. 代码模板

def next_greater(nums: list[int]) -> list[int]:
    """ans[i] = 右边第一个大于 nums[i] 的下标;不存在为 -1。"""
    n = len(nums)
    ans = [-1] * n
    stack: list[int] = []          # 存下标,对应值从栈底到栈顶递减
    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            ans[stack.pop()] = i   # 弹栈即回答
        stack.append(i)
    return ans

4. 常见错误

1. 栈里存值而不是下标——答案要的是位置，存值就丢了；
2. 弹栈条件带不带等号与题意不一致（见边注）；
3. 循环数组（LeetCode 503）忘记用取模遍历两倍长度；
4. 忘记处理「栈里剩下的元素」——它们答案为 -1，初始化时已覆盖，别在结尾重复赋值。

5. 待补充

• 柱状图中最大矩形（LeetCode 84）：弹栈时的宽度计算；
• 环形数组的两遍扫描技巧；
• 单调队列与滑动窗口最大值的对照。

6. 相关练习

• LeetCode 496 / 503 · 下一个更大元素 I/II；
• LeetCode 739 · 每日温度——最干净的应用；
• LeetCode 84 · 柱状图中最大的矩形——等这篇补充完再来。

上一篇回顾：044《并查集：把等价关系收进森林》。