什么是单调栈？它能解决哪一类问题？

简化版

单调栈是一个栈内元素始终保持单调递增或递减的栈：新元素入栈前，把栈里所有「破坏单调性」的元素先弹出。它专门解决**「找每个元素左边/右边第一个比它大（或小）的元素」**这类问题，比如「下一个更大元素」「每日温度」「柱状图最大矩形」。每个元素只进出栈一次，整体 O(n)。

详细版

普通做法找「每个元素右边第一个更大的数」要对每个元素向右扫，O(n²)。单调栈把它降到 O(n)。

以「下一个更大元素」为例，维护一个从栈底到栈顶递减的栈，存下标：

int[] nextGreater(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Arrays.fill(res, -1);                    // 默认没有更大的
    Deque<Integer> stack = new ArrayDeque<>();  // 存下标，对应值单调递减
    for (int i = 0; i < n; i++) {
        // 当前元素比栈顶大 → 栈顶找到了它的「下一个更大元素」
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            res[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return res;
}

关键：当前元素比栈顶大时，不断弹栈，被弹出的那些元素的「右边第一个更大值」就是当前元素。

完整版教学

一、单调栈的核心思想

单调栈解决的是一个反复出现的诉求：对每个元素，找到它某一侧第一个「更大/更小」的元素。暴力是双重循环 O(n²)。单调栈的洞察是：如果一个元素比它前面的某些元素大，那么前面那些「更矮的」元素以后再也用不到了（它们被当前更大的元素「挡住」了），可以直接从栈里弹掉。这样每个元素只入栈、出栈一次，总复杂度 O(n)。

二、为什么保持单调性

以「找右边第一个更大元素」为例，栈里维护的是「还没找到更大元素的候选」，它们从栈底到栈顶递减。当新元素来了：

如果它比栈顶大，说明它就是栈顶元素苦苦等待的「右边第一个更大值」，弹出并记录。
一直弹到栈顶比它大（或栈空）为止，然后自己入栈等待。

栈内始终递减，所以叫「单调递减栈」。找「更小」就维护递增栈，方向相反。

三、四种组合怎么记

「找更大还是更小」×「找左边还是右边」共四种。记忆口诀：

求下一个更大 → 单调递减栈（栈顶到栈底递增），遇到更大的就弹。
求下一个更小 → 单调递增栈，遇到更小的就弹。
找右边：正向遍历；找左边：反向遍历（或看弹栈后新栈顶）。

不用死记，理解「栈里存的是还没被解决的候选，来了个能解决它们的元素就批量弹出」即可推导。

四、经典应用

每日温度：res[i] = 还要等几天才有更高温度 → 递减栈存下标，差值即天数。
下一个更大元素 I / II：II 是循环数组，遍历两遍（i % n）即可处理环形。
柱状图中最大的矩形：单调递增栈，弹栈时以「被弹柱子的高度」为高、算能扩展的宽度。
接雨水：单调递减栈，弹栈时按「凹槽」积水。
股票跨度、去除重复字母等也用它。

五、实现要点

存下标而非值：往往需要用下标算距离/宽度，存下标更灵活（用时 nums[stack.peek()] 取值）。
循环数组：遍历 2n 次、下标取 i % n，模拟绕一圈。
初始化默认值：没有更大元素的位置填 -1。
想清楚「递增还是递减」「弹栈时机是 > 还是 >=」（重复元素的处理）。

六、常见误区与追问

目标	栈内维护	弹出条件	常见题
找右侧第一个更大	单调递减栈	当前值更大时弹出	每日温度
找右侧第一个更小	单调递增栈	当前值更小时弹出	柱状图边界
找左侧第一个更大	从左到右扫	弹完后看栈顶	股票跨度
找左右边界	两次扫描或一次结算	视边界定义而定	最大矩形

记忆钩子：单调栈里留下的是“还没找到答案的候选人”。当前元素一旦能替它们结算，就把它们弹出并记录答案。

以温度 [73,74,75,71,69,72,76] 为例，维护下标递减栈。第 1 天 73 入栈；第 2 天 74 比 73 高，弹出第 1 天并得到等待 1 天；第 7 天 76 会连续弹出多个比它低的下标。每个下标最多入栈一次、出栈一次，所以总复杂度是 O(n)，不是看起来的 O(n²)。

误区：单调栈每次都要和栈内所有元素比较。 实际只和栈顶比较，弹出的元素不会再回来，因此总操作数线性。
误区：栈里应该存值，不需要存下标。 很多题要计算距离或边界宽度，通常必须存下标；值可通过数组访问。
误区：递增栈和递减栈可以随便选。 要找更大还是更小、找左边还是右边，会决定维护方向和弹出条件。
追问：为什么单调栈是 O(n)？ 每个元素最多入栈一次、出栈一次，while 的总弹出次数不超过 n。
追问：相等元素怎么处理？ 要看题目要求“严格大于/小于”还是“大于等于/小于等于”，等号决定是否弹出。
追问：单调栈和单调队列区别是什么？ 单调栈解决最近更大/更小边界，单调队列还要维护窗口范围，常用于滑动窗口最值。

七、加强记忆

单调栈 = 栈内元素保持单调（递增或递减）的栈，入栈前弹掉破坏单调性的元素。专治**「找每个元素左/右第一个更大或更小」：求下一个更大用递减栈**、更小用递增栈，遇到能解决栈顶的元素就批量弹出并记录。每个元素只进出一次，O(n)。常存下标，经典题有每日温度、柱状图最大矩形、接雨水。

简化版

详细版