优化实战)
1. 先从“找一个比他高的小朋友”说起：暴力解法的瓶颈
做算法题的都知道，“单调栈”这三个字一提出来，好多人都觉得是个高级货。其实说穿了，它就是栈里保持单调性的技巧。别被名字唬住，我见过太多人把单调栈当成一个数据结构去背模板，结果换个题目就不知道怎么用了。真正要理解的，是它到底解决了个什么问题。
最近有个热搜词特别有意思，叫“算法 找下一个身高更高的小朋友”。这个描述特别形象——一排小朋友按顺序站着，问你每个小朋友右边第一个比他高的人是谁。这其实就是LeetCode上经典的“每日温度”问题换了个皮：给你一个数组，对每个元素找右边第一个比它大的元素距离有多远。这类题，不懂单调栈的人第一反应就是暴力枚举——两层循环，每个元素都往后扫一遍，找到第一个比它大的就停。我当时第一次写的也是这种：
public int[] bruteForce(int[] nums) { int n = nums.length; int[] res = new int[n]; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (nums[j] > nums[i]) { res[i] = j - i; break; } } } return res; }代码是挺好写的，逻辑也好理解，但时间复杂度和空间复杂度一算就露馅了。最坏情况下数组是降序排列，比如[5,4,3,2,1]，每个元素都要往后扫到数组结尾才发现找不到目标，两层循环全部跑满，复杂度是 O(n²)。几百个数据量倒是无所谓，一旦数据量到十万级、百万级，这个复杂度在一众算法面试题里基本就是送命题。
那有人会问，能不能用二分查找或者预处理辅助数组优化一下？比如先从右往左预处理一个“当前位置之后的最大值”出来，然后配合二分去找第一个大于当前值的下标。这个思路确实能把时间复杂度降到 O(n log n)，但实现起来麻烦不说，还有个隐含的问题：你要“第一个”比它大的，而不是“任何一个”比它大的。二分只能找到一个大于它的位置，没法保证是第一个。你再想想怎么判断“第一个”，还是得引入额外状态。
所以单调栈的价值就在这里：它能用一次遍历，在 O(n) 时间内拿到每个元素右侧第一个更大元素的信息，而且不需要额外数组，代码也只有十几行。理解它值不值，先理解这个“为什么需要它”就够了——单调栈不是炫技，它是暴力解法在大数据量下暴露问题之后，顺理成章长出来的优化产物。
2. 单调栈的核心机制：维护单调性与结算时机
2.1 递增栈和递减栈到底怎么选
很多教程上来就说“单调栈分递增栈和递减栈”，然后给出两套模板，让大家背。我先跟你说结论：单调栈没有所谓固定的“递增”或“递减”模板，选择用哪一种，取决于题目要你找的是“左右两边第一个更大的”还是“左右两边第一个更小的”。
我们来拆一层窗户纸。栈里存的是数组中还没结算答案的元素下标，栈内元素对应的值始终保持单调——这个“单调”的方向，本质上是你在遍历过程中把不符合单调性的元素弹出去留下的结果。用“下一个身高更高的小朋友”举例，我们要找右边第一个比他高的，那栈就要维护成单调递减：栈底到栈顶，对应身高从高到低。
为什么？因为只有栈里的元素从栈底到栈顶严格递减（或者非严格，细节后面说），当你遍历到一个新元素时，如果它比栈顶元素高，那它恰恰就是栈顶元素一直等待的“右边第一个更高的”。此时把栈顶弹出并记答案，继续判断新的栈顶——如果新元素还是更高，那它也是这个新的栈顶元素等待的答案。一直弹到栈为空，或者栈顶元素不再比当前元素小。
反过来，如果题目要求找“左右两边第一个更小的”，比如经典的柱状图最大矩形，你就得用单调递增栈：栈底到栈顶从低到高。遇到比栈顶小的元素时，栈顶元素等到了它右侧第一个更小值，弹出去结算。方向反了，答案是错的，代码再漂亮也没用。
2.2 弹出的那一刻才是答案结算的时刻
这是单调栈最核心的思想，也是我在教别人时反复强调的一句话：答案不是在入栈时算的，而是在出栈时算的。
为什么？因为入栈的时候，你还不知道右边会在什么时候出现一个比它更大的元素，信息不足，答案无法确定。而出栈的时候，恰恰就是“右边第一个更大元素”出现的时候——就是当前遍历到的这个元素。此时你手里握着两个信息：栈顶元素的下标索引，和当前元素的下标索引。两者之间的差值就是距离，也就是答案。
拿“每日温度”来说，栈里存下标，遍历到temperatures[i]时，只要temperatures[i] > temperatures[stack.peek()]，就说明栈顶这一天等到了第一个更热的日子，弹出栈顶idx，让ans[idx] = i - idx。这一步就是把“等待”化为“结算”。整个过程每个元素只会入栈一次、出栈一次，所以总复杂度 O(n)。
我给这个模板起名叫“结算模板”——它在我脑子里比“单调栈模板”更让人记得住：
Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < nums.length; i++) { while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) { int idx = stack.pop(); // 此时 nums[i] 就是 nums[idx] 右侧第一个更大的 ans[idx] = i - idx; } stack.push(i); }注意一个细节：弹栈的那个 while 循环判断条件用的是nums[i] > nums[stack.peek()]，等于时不弹。这个等号的处理有讲究，我在第 4 章专门展开聊，先记住“大于才弹”。
3. 从裸题到变形题：四类题型的破题路径
3.1 最直观：下一个更大元素与每日温度
LeetCode 496、739 这类题目是单调栈的“主战场”。它们的共同点是：给一个数组，要求每个元素右侧第一个比它大的元素。解法就是我上面给的那个模板，几乎是直接抄。区别只是 496 多绕了一层“在 nums1 和 nums2 之间建立映射”，核心还是对一个数组跑一遍单调栈，记录每个元素的右边更大值，然后再去查 nums1。
我见过不少人一上来就想用“每个元素跟后面所有元素比较”的暴力法，写完了还觉得没问题，等数据量一大就直接超时。实际上 LeetCode 739 的题干数据量就是刻意设计来卡暴力解的——temperatures最长 10 万，O(n²) 基本跑不动。你用单调栈，一遍遍历完事。这就是为什么它经典，因为它是“用空间换时间、把无用比较彻底删掉”的最直观示范。
3.2 双方向都要用：柱状图中最大的矩形
LeetCode 84 是升华题。它不只是找右边第一个更小的，而要同时知道左边第一个更小的位置，才能确定一个柱子能向左向右扩展多远，从而算出以它为高的矩形最大能有多大。
这道题的暴力想法是：枚举每根柱子作为矩形的高，然后分别向左、向右找到第一个比它矮的柱子，两个边界之间的宽度乘以这个高，就是它能形成的最大矩形。这样每个柱子要往两边扫，仍然是 O(n²)。优化的思路就是，在遍历过程中，同时把“左边第一个更矮”和“右边第一个更矮”都记下来。
这时候需要两个方向各跑一遍单调栈：一次从左到右，求出left[i]表示 i 左边第一个比heights[i]矮的下标；一次从右到左，求出right[i]表示 i 右边第一个比heights[i]矮的下标。遍历完两个方向后，对每个 i 直接用heights[i] * (right[i] - left[i] - 1)算面积取最大值。这段逻辑本身不难，难的是很多人第一反应想不到“两个方向各跑一次”。
也有更巧妙的“一遍遍历+哨兵”写法，我用它作为面试时的首选方案：
public int largestRectangleArea(int[] heights) { int n = heights.length; // 前后各加一个高度为0的哨兵，避免处理栈空和遍历结束时的额外判断 int[] h = new int[n + 2]; System.arraycopy(heights, 0, h, 1, n); h[0] = 0; h[n + 1] = 0; Deque<Integer> stack = new ArrayDeque<>(); stack.push(0); // 先放左哨兵 int ans = 0; for (int i = 1; i <= n + 1; i++) { while (h[stack.peek()] > h[i]) { int height = h[stack.pop()]; int width = i - stack.peek() - 1; ans = Math.max(ans, height * width); } stack.push(i); } return ans; }h[n + 1]那个右哨兵高度为 0，能把栈里所有剩下的柱子全部逼出来结算。这个技巧我建议你记住，因为它省掉了“遍历完了还要把栈清空”的收尾判断，代码简洁很多。
3.3 由面积思维转向体积思维：接雨水
LeetCode 42 接雨水，网上解法多得吓人，双指针、动态规划、单调栈都能做。但用单调栈解这道题，理解的是“积水是逐层算的”还是“逐列算的”，想清楚了代码会非常短。
我讲讲单调栈做法里的一个思考转折。前面几道题，出栈即结算，结算的是“左边等待的那个元素”的答案。而接雨水不同：当height[i] > height[stack.peek()]时，我们把栈顶弹出，这个弹出的元素相当于是“凹槽底部”，然后看新的栈顶——如果栈不为空，那新栈顶和当前 i 之间的水平距离乘以“两边较低的高度减去凹槽高度”，就是这一段能接的雨水。它画出来是横向分层的一小条面积。
public int trap(int[] height) { int ans = 0; Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < height.length; i++) { while (!stack.isEmpty() && height[i] > height[stack.peek()]) { int bottom = stack.pop(); if (stack.isEmpty()) break; int left = stack.peek(); int width = i - left - 1; int h = Math.min(height[left], height[i]) - height[bottom]; ans += width * h; } stack.push(i); } return ans; }这道题很容易踩的坑是：弹出后没有检查栈空了就直接计算，于是把“左边没有挡板”的那部分也算了进去。积水的必要条件是有左墙、有右墙、有凹槽，三者缺一不可。我在代码里写了if (stack.isEmpty()) break;就是为了处理左侧没有更高柱子、无法形成储水凹槽的情况。
3.4 脱离“比大小”：去除重复字母保持最小字典序
LeetCode 316/1081 这道题，看起来跟单调栈八竿子打不着，但它的核心思路仍然是“用单调栈维护一个字典序最小的序列”。很多人做不出来，是因为没意识到单调栈里的“单调”不一定指数字大小，也可以指字符的字典序。
问题要求是：删除一个字符串中的重复字母，使得每个字母只出现一次，并且返回的字符串在所有可行结果中字典序最小。如果只是去重，很简单，用个 HashSet 就行。但要求字典序最小，就需要在当前字符比栈顶字符更小时，考虑把栈顶字符弹出去——前提是这个栈顶字符后面还会再出现，否则弹掉它就彻底丢失了。
例如字符串"bcabc"，处理到a时，前面栈里有['b','c']，a比它们都小，但b和c在后面还会出现，所以可以把它们弹掉，换成a在更靠前的位置，这样字典序就更小了。显然这里是字符之间的字典序比较，我写的判断条件就是stack.peek() > c，配合一个“某个字符是否还在后续出现”的预统计来保证不弹掉永远不会再出现的字符。
这类题的破题点在于：单调栈不一定比较数值，任何有“顺序”关系的东西都可以比较。一旦理解到这一层，你就能把单调栈用到很多想不到的地方。
4. 边界条件与高频错误：这些坑我替你们提前踩了
4.1 单调方向弄反
这个坑出现频率最高。面试官随意改一个词，把“下一个更高”改成“下一个更矮”，你还在照抄上一题的模板，必挂。怎么规避？我给自己定了条规则：每次动手前先问一句“我要找的是更大的还是更小的”。找更大的，栈里维持递减（栈底大、栈顶小），当前值比栈顶大就触发弹栈；找更小的，栈里维持递增，当前值比栈顶小就触发弹栈。
还有个更直观的理解：触发弹栈的条件就是“当前元素抢走了栈顶等待的答案”。你要找更大的，那当前元素只有在比栈顶更大的时候，才有资格成为栈顶的答案，对吧？所以条件是>，栈就是递减栈。你要找更小的，那当前元素只有比栈顶更小，才能成为答案，条件是<，栈就是递增栈。顺着这个逻辑想，就不会记反。
4.2 存下标还是存值？这里有个隐蔽的雷
这个问题在 LeetCode 496 这种“只要值”的题里不致命，但一旦到了求距离、求宽度的题里，存错就是双击报废。单调栈里存的一律建议是下标，不是值。
原因是：你弹出栈顶后，除了要知道它的值，还要知道它的位置——位置用来算距离，位置对应到数组里取值才是它的值。而且结算的时候，栈里相邻元素的下标差，就直接决定了“左边界在哪”。如果你存的是值，弹出之后你根本无法知道它原本在数组的哪个位置，i - idx这种距离就算不出来了。这是我见过的最常见低级错误，也是很多人调试半天才发现的问题。
4.3 相等元素怎么处理：用>还是>=
这个细节很多人忽略，但它直接决定答案对不对的同时还会影响效率。你问的是“第一个更大/更小”，那相等当然不算。所以在“下一个更大元素”这类题里，条件必须是nums[i] > nums[stack.peek()]，等于的时候不能弹，否则相等元素会互相干扰答案，导致结果出现 0 和 1 的偏差。
但在“柱状图中最大矩形”这种题里，为了计算宽度方便，处理相等的柱子时最好取一个能确保面积正确的方式：如果左右两端用>=弹出，相等的柱子会把左边界一直推到更左边，最终宽度计算不会把相等柱子漏掉。我的经验是：求“下一个更大/更小”用严格不等号；求“边界扩展范围”用非严格不等号，再配合哨兵保证栈不会空。这个规则我用下来几乎没有出过问题。
4.4 栈空判断与哨兵技巧
栈空处理是最容易写出 bug 的地方。比如求“下一个更大元素”时，如果栈为空或者当前元素不够大，直接入栈就行，不会出错。但接雨水那道题里，弹出 bottom 后如果栈立刻为空，说明左侧没有更高的墙，就别算面积了。
我在处理很多单调栈题时都会用“哨兵”技巧——在数组头尾塞一个虚拟元素，减少边界判断。比如柱状图最大矩形里，数组头尾加高度为 0 的哨兵，这样栈永远不会真的空，遍历结束时 0 会把所有剩余元素逼出来结算。这是工程上非常实用的技巧，省掉一堆 if-else。
5. 从刷题到工程：单调栈的真实投影与延伸思考
5.1 连续数据流场景：股票价格跨度
LeetCode 901 股票价格跨度，是单调栈在“在线算法”场景下的一个代表。它要求你设计一个类，每次next(price)传入一个新的价格，返回“今天价格连续小于等于今天价格的天数”——其实就是从今天往前数，连续多少个交易日的价格都不超过今天。
这类问题用暴力法是每次都往前回溯，遇到大波动数据时平均复杂度很高。单调栈的做法是每天都把栈里小于等于当天价格的那些“跨度”累加起来，然后合并成一个新的节点压栈。我维护一个存{价格, 跨度}的栈，每次来新价格，把所有小于等于它的栈顶节点弹出，把它们的跨度累加到 1 上，再压入新节点：
class StockSpanner { private final Deque<int[]> stack = new ArrayDeque<>(); private int index = -1; public StockSpanner() { stack.push(new int[]{Integer.MAX_VALUE, index++}); } public int next(int price) { index++; while (stack.peek()[0] <= price) { stack.pop(); } int span = index - stack.peek()[1]; stack.push(new int[]{price, index}); return span; } }刚看这个代码可能会觉得：这不就是维护一个递减栈吗？对，它本质上还是“维护一个从近到远价格递减的结构”。为什么幅度大的时候性能好？因为小的跨度被提前合并成了大跨度，后续的新价格只需要跟大跨度比较，小的那些中间过程早就被丢弃了。这个“合并后再压栈”的思路，是单调栈在数据流问题里的一个独特点：出栈时结算的不只是单个元素的答案，而是把多个元素的信息聚合成一个新节点，继续参与后续的比较。
5.2 单调栈和单调队列，别把它们搞混了
刷题刷到后面，很多人会把单调栈和单调队列（Monotonic Queue）搞混。我经常用一个很简单的区分方式：栈解决的是“窗口内有边界和当前位置的关系”的问题，队列解决的是“滑动窗口中维护极值”的问题。
单调队列经典应用是滑动窗口最大值。它的核心是队头弹出过期元素（在窗口之外），队尾维持单调性——新元素比队尾大就把队尾弹掉。你会发现它和单调栈很像，都利用了“不合时宜的旧元素直接淘汰”的思维，但一个从队尾进出、一个限制了窗口生命周期，两者处理的约束条件完全不同。
面试中如果能主动把这两者对比着讲，是个很加分的点。我面试别人的时候，问单调栈的题经常追加一句“如果这个数组变成了滑动窗口，你还能用 O(n) 解出来吗？”——这时就需要切到单调队列的思路上了。
5.3 为什么这个 O(n) 是货真价实的
最后聊一个容易被忽视但面试官爱问的点：为什么单调栈是 O(n) 而不是 O(n²)？
你看 while 循环里似乎在反复弹栈，好像每个元素都可能把前面弹一遍。但你要想清楚：每个元素最多入栈一次、出栈一次。不管 while 循环里弹了多少个，这些元素都是之前入栈过的，弹出去之后就不会再进来了。所以总弹栈次数 ≤ 总入栈次数 = n。每个元素的操作是常数次，总复杂度就是 O(n)。
这个“每个元素入栈出栈各一次”的摊还分析，是单调栈所有题目的复杂度基石。理解它比背十几行模板有用多了。很多人觉得单调栈难，其实难不在代码，难在想清楚“为什么这些弹出的操作累加起来不是 O(n²)”——想明白了，整个数据结构就通透了。
我个人刷题的经验是：不要把单调栈当做一个独立的算法去记，而是当成一种“延迟比较、遇到强敌统一结算”的思维工具。遇到一个题，先问自己：是不是每个元素都等着找一个比它大/小的邻居？如果是，就可以考虑单调栈；然后再问，我需要左边的信息还是右边的信息？需要两边的就两次循环处理；最后问，我要比的是数值还是字典序还是其他的顺序关系？把这三个问题问完，绝大部分单调栈题就都能落到你熟悉的模板上了。希望这篇对你有用，至少下次再遇到“找一个比他高的小朋友”这类题，不用再老老实实两层循环跑到超时了。
