单调栈专题导读

何时想到单调栈

单调栈（Monotonic Stack）解决的问题非常聚焦，一句话就能描述：为序列中每个元素，找到它左侧或右侧第一个比它大（或小）的元素。

判断该不该上单调栈，看题目是否带有这类信号：

• "下一个更大元素 / 前一个更大元素"（显式信号）；
• "距离下一次更暖和的天数"（隐式信号，本质还是下一个更大）；
• "以每个元素为最小值/最大值能扩展多宽"（柱状图、接雨水的底层模型）；
• 暴力解法是"对每个元素向左/右扫描"的双重循环（O(n²) 起步，多半可以单调栈优化）。

为什么单调栈能解决？关键在于一个观察：当新元素比栈顶大时，栈顶元素"右侧第一个更大元素"已经找到了——就是当前这个新元素。栈顶的答案一旦确定，它就可以出栈，把位置让给还没确定答案的元素。每个元素都在"帮栈顶找答案"，这就是单调栈的全部直觉。

模板：递增栈还是递减栈

单调栈分两种，命名按栈内元素从栈底到栈顶的趋势：

记忆方法：栈顶是新元素要"解答"的对象。新元素能把栈顶弹掉，说明栈顶等的就是它。想找"更大"就保持递增栈，新元素进来时把所有比它小的都弹出去；想找"更小"反之。

通用模板（以"下一个更大元素"、单调递增栈为例）：

// 求每个元素右侧第一个比它大的元素，不存在则记 -1
int[] nextGreater(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Deque<Integer> stack = new ArrayDeque<>(); // 存下标！
 
    for (int i = 0; i < n; i++) {
        // 当前元素大于栈顶下标对应的值：栈顶的答案就是 i
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            int top = stack.pop();
            result[top] = nums[i]; // 或记 i - top（距离类问题）
        }
        stack.push(i); // 自己入栈，等后续元素来解答
    }
    return result;
}

模板只有三个动作：比不过就压栈、比得过就弹栈结算、循环结束后栈里剩的是没有答案的元素（如上例记 -1）。全部逻辑 10 行以内。

为什么存下标而不是值

模板里栈存的是下标，这是新手最常问的问题。原因有三：

1. 答案需要位置信息："距离下一次更暖的天数"要算 i - top，只有下标能算；
2. 弹栈时要回看值：比较用 nums[stack.peek()]，存下标顺带把值也拿到了，反过来只存值就丢掉了位置；
3. 接雨水、柱状图需要左右边界：宽度 = 右边界下标 - 左边界下标 - 1，纯值无法参与几何计算。

例外也存在：如果题目只要求返回值、且用 HashMap 可以额外建立"值 → 答案"的映射（如 496 的子序列版），存值也能做。但统一存下标是更通用的肌肉记忆。

还有一个隐含的好处：下标天然不重复。如果序列里有相等元素，直接拿"值"当 HashMap 的键或栈的比较对象容易在去重语义上踩坑（相等算不算更大？）；而下标是唯一的，栈内每个下标独立结算，去重逻辑完全由比较条件显式控制，行为可预期。

O(n) 均摊复杂度

看模板里的 while 套在 for 里，直觉上像 O(n²)，实际上整体是 O(n)。证明用均摊（计数）分析：

• 每个元素至多入栈一次、至多出栈一次；
• 所有元素的入栈总次数 ≤ n，出栈总次数 ≤ 入栈总次数 ≤ n；
• 内层 while 的总执行次数被出栈次数限制住，所以两层循环的总操作数 ≤ 2n。

这就是典型的均摊分析：单次循环最坏可达 O(n)，但平摊到每个元素身上只有 O(1)。对比暴力解法"每个元素向右扫描找第一个更大"，O(n²) → O(n) 的提升全部来自"出栈的元素不再参与后续比较"。

一个重要的重复元素细节：序列里有相等元素时，弹栈条件用 > 还是 >= 会影响行为。求"下一个严格更大"用 >（相等元素留在栈里等真正更大的）；求"下一个大于等于"用 >=。接雨水、柱状图等题对这条边界的处理直接决定正确性，写题时先想清楚相等算不算。

适用信号总结

把"何时上单调栈"整理成一张速查表：

最后补充一条"不该用"的信号：如果题目问的是全局最大值/最值对（如全局最大温差），排序或一次扫描就够，不需要为每个元素都找答案——单调栈的价值在于"每个元素都要一份答案"，没有这种全员结算需求时不要套模板。

LeetCode 题单清单

本专题 5 道核心题，建议严格按顺序刷：

学习建议

• 先吃透 739：它是所有单调栈题的母题，把"每个元素进出栈各一次"和"弹栈即结算"两个动作亲手模拟一遍；
• 模拟时画栈：拿 [73,74,75,71,69,72,76,73] 手工模拟一遍入栈出栈过程，画出每一步栈内下标，比看十遍文字都管用；
• 弹栈时多问一句：为什么此刻栈顶的答案确定了？确定的是"右边第一个更大"还是"积水宽度"？把这个问题贯穿到每一题。

下一篇进入实战：每日温度逐行讲模板，循环数组的取模技巧，接雨水三种解法对比，以及柱状图最大矩形的哨兵写法。

参考

• 代码随想录 · 单调栈专题