栈里只留”还在等下一个更大元素”的候选人。新人 进来,把所有 的栈顶通通弹掉 —— 它们的”下一个更大”就是 。每个元素进栈一次出栈一次, 收工。

直觉 — “把栈顶不可能成为答案的元素弹掉”

正向思考”对每个 找右边第一个比它大的”是 。换一个视角: 反过来,每个新元素 主动认领自己是谁的答案。

栈里维护一列”还没找到下一个更大元素的候选人”的下标,从栈底到栈顶严格递减(谁更早进来谁更大)。当 进来:

• 栈顶 ? 说明 就是栈顶的”下一个更大”。弹掉,登记答案。
• 接着比下一个栈顶,直到栈顶 或栈空。
• 入栈,排队等自己的”下一个更大”。

每个下标进栈一次、出栈至多一次 —— 总操作 ,均摊 。

一句话: 栈和目标反着来。想找更大的,栈里存的是从大到小排列的候选人。

动画 — 跟着栈顶的颜色看

下面的动画跑数组 [2, 1, 5, 6, 2, 3] 找”下一个更大元素”。一步一步点,盯紧三件事:

1. 绿色是当前正在访问的 nums[i]。
2. 青色是还在栈里、还没找到答案的候选人。
3. 红色是这一步被 x 弹出的栈顶 —— 它头顶冒出的 →x 就是登记的答案。

特别注意 5 进来时一口气把 1, 2 都弹掉,以及 6 把 5 也弹掉 —— 这就是” 均摊”的真身: 一次性还多次旧债。

看完动画,栈的形状永远是一个递减的青柱阶梯。这个画面是单调栈的根本记忆点。

一个模板,四种变种

模板就一个,改两处即可。目标和栈的单调性相反,这是核心。

目标	栈的单调性 (底→顶)	while 比较	遍历方向
下一个更大	递减	nums[top] <= x	从左到右
下一个更小	递增	nums[top] >= x	从左到右
上一个更大	递减	nums[top] <= x	从右到左
上一个更小	递增	nums[top] >= x	从右到左

口诀: “大递减,小递增;左找反着走,右找正着走。”

至于比较里要不要带等号,看是否允许相等元素互为答案,默认带上更稳。

模板代码 — 每日温度 (LC 739)

返回每天要等多少天才能遇到更暖的一天。把”找下一个更大”的答案从值改成下标差即可:

def dailyTemperatures(T):
    n = len(T)
    ans = [0] * n
    stack = []  # 存下标,栈底到栈顶对应温度递减
    for i, x in enumerate(T):
        while stack and T[stack[-1]] < x:
            j = stack.pop()
            ans[j] = i - j        # x 是 j 的下一个更大,距离就是答案
        stack.append(i)
    return ans

为什么存下标不存值: 还要算距离、宽度、窗口范围。存值就丢了位置信息。所有单调栈题,默认存下标。

进阶 — 柱状图最大矩形 (LC 84)

思路: 枚举”以哪根柱子做高”的最大矩形。要确定宽度,得知道左、右两侧第一个比它矮的柱子在哪。这正好是”上一个更小 + 下一个更小”两个变种 —— 用同一个栈一次扫完。

def largestRectangleArea(heights):
    heights = [0] + heights + [0]      # 首尾哨兵,省掉边界判断
    stack, ans = [], 0
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            mid = stack.pop()
            # 弹出 mid 时: 右边第一个更小是 i, 左边第一个更小是新栈顶
            ans = max(ans, heights[mid] * (i - stack[-1] - 1))
        stack.append(i)
    return ans

两个哨兵 0 的作用:

• 末尾的 0 强制清空栈中所有真柱子,统一在循环里处理。
• 开头的 0 充当左边界,确保弹出时 stack[-1] 永远不越界。

接雨水 (LC 42) 同样套路: 弹出栈顶 mid 时,左侧是新栈顶,右侧是 i,这一层能接的水是 。“弹出即结算”是单调栈解几何类问题的统一招式。

记忆法

一句话: “栈顶被 打败, 就是栈顶的答案。”

三步走:

1. 看题型: 出现”下一个/上一个 更大/更小”、”右边第一个比 … 矮/高”、”柱状图/雨水”。→ 条件反射写单调栈。
2. 定方向: 找”更大”用递减栈,找”更小”用递增栈。栈和目标反着来。
3. 弹出即结算: while 循环里弹栈顶时,当前 i 和新栈顶分别是它的右、左边界 —— 距离、宽度、贡献都在这一瞬间算完。

判断口诀:

• 单点 + “下一个 X” → 单调栈
• 滑窗 + “区间最值” → 单调队列(加个过期检查)
• 离线 + “比较类查询” → 离线扫 + 单调栈

LeetCode 必刷: 496, 739, 503(热身); 84, 42, 85, 907, 316(进阶)。