说实话这类题我在不同场合见过很多次形态从“找右边第一个比它大的数”到“找左边第一个比它小的数”再到那些看起来更复杂的柱子、温度、接雨水问题本质都绕不开同一个东西单调栈。我第一次接触的时候也很头大因为左右、大小一组合就是四种情况网上教程往往每一种单独讲背完四个模板还是容易混。后来我把它整理成一个通解之后发现自己再也不用在这一类题目上花太多时间了。这篇文章就是对这个通解的完整记录。我会先讲清楚为什么单调栈能一次遍历解决问题然后给出一个可以同时处理左/右、大/小四类关系的统一模板再结合几个高频实战题目拆解套用方式最后把我踩过的相等元素、方向写反、空栈取值这些坑全部翻出来。无论你是准备算法面试还是在业务代码里碰到“区间统计”类需求这套东西应该都能直接帮你省下不少时间。1. 问题全景与通解思路1.1 这类问题在真实业务里长什么样先看几个场景有一个城市逐日温度记录想知道每一天之后要等几天才能遇到更高温度有一个股票价格序列想找每个交易日之前最近的高点和之后最近的低点再比如有一排柱子的高度想求能勾勒出的最大矩形面积。这些场景落到抽象层面都是同一个模式给定一个数组对每个位置求某个方向上第一个满足大小关系的位置。关键点是“第一个”不是“最大的那个”也不是“最小的那个”。这意味着每个位置的答案只取决于离它最近的那个满足条件的元素。这个语义和“可见性”很像可以想象排队买票的场景每个人都想看到自己前面第一个比自己高的人矮个子会被前面的人挡住而高个子也可能被更高的挡住所以每个人真正关心的其实只是离自己最近的那个遮挡关系。暴力解当然能做两层循环逐个扫时间 O(n^2)。数组长度到 10^5 的时候暴力大概要跑 5e9 次比较一般机器上几十秒都跑不完。而单调栈的做法是 O(n)每个元素只入栈出栈各一次整体操作量在 2e5 量级。这个差距不是优化一点的问题是能不能算完的问题。1.2 从暴力到单调为什么栈恰好合适暴力慢在哪里慢在很多比较都是重复的。比如数组 [3,1,4,2]求每个元素右边第一个更大的数字。位置 1 的值 1 扫到 4 就停下来了位置 0 的值 3 却还要重新经过 1、4而 1 和 4 在上一轮已经被扫过了。这些重复访问就是 O(n^2) 的来源。单调栈的思路是维护一个“还没找到答案的候选集”。候选集中在栈里栈内元素的值按照某种顺序保持单调。每来一个新元素先和栈顶比较如果它能把栈顶“淘汰”掉就把栈顶弹出并且在这个瞬间确定栈顶元素的答案。如果它不能淘汰栈顶就入栈等待。这样做的结果是每个元素最多被比较一次不会出现重复扫描。1.3 通解的四个象限把“左/右”和“大/小”组合起来一共是四种情况。我习惯用一张表把它们固定住目标遍历方向当前元素成为栈顶答案的条件右侧第一个更大从左到右新元素 栈顶元素右侧第一个更小从左到右新元素 栈顶元素左侧第一个更大从右到左新元素 栈顶元素左侧第一个更小从右到左新元素 栈顶元素注意看触发条件其实只有两套找“更大”就是当前元素大于栈顶时弹出找“更小”就是当前元素小于栈顶时弹出。剩下的变量只有方向。这个观察是整套通解的基石。2. 单调栈核心原理与一次遍历的完整推演2.1 栈里存下标别存值先记住一个最重要的规范栈里存下标不要存值。下标可以通过nums[i]随时取到值但值无法反向拿到下标。而且很多问题最终要的是位置距离比如“再等几天”“相隔几个位置”没有下标根本算不了。还有一个隐藏原因是为了区分相等元素。如果存的是值两个相同的数字在栈里会出现同值不同位的情况出栈时根本不知道该给哪个位置写答案。下标是唯一的天然不会造成这种混淆。2.2 手工推演右侧第一个更大的完整过程拿一个短数组 [2, 1, 4, 3, 2] 手动走一遍。目标是每个位置右侧第一个比它大的下标不存在则返回 -1。步骤当前下标和值操作出栈结果栈内情况1i0, val2入栈-[0(2)]2i1, val11 不大于 2入栈-[0(2), 1(1)]3i2, val44 1弹出 14 2弹出 0res[1]2, res[0]2入栈后 [2(4)]4i3, val33 4入栈-[2(4), 3(3)]5i4, val22 3入栈-[2(4), 3(3), 4(2)]循环结束后栈里剩下的下标 2、3、4 对应值 4、3、2它们在右侧都没有更大的元素所以结果保留初始值 -1。最终答案是[2, 2, -1, -1, -1]。这里有个细节值得注意当 4 到达时先弹出 1再弹出 2。弹出顺序是离当前位置最近的先出、更远的后出这正好符合“第一个”的语义。如果某个元素在栈里一直没被弹出说明它始终没遇到比自己更大的元素一旦遇到了出栈的瞬间答案就确定了之后不可能再被另一个更大的元素覆盖因为“第一个”已经出现了。2.3 为什么单调性能保证“第一个”可以这样理解栈内从栈底到栈顶对应元素的值是保持单调的。以“右侧第一个更大”为例栈内值是递减的。如果栈里相邻两个元素出现了逆序比如上一个位置的元素比较小、下一个位置的元素比较大那么左边那个较小的元素在右边那个较大的元素入栈时就已经被处理过不可能还留在栈里。这个规则保证了栈顶元素永远是距离当前位置最近的那个“还在等待答案”的候选者。所以每次新元素来的时候只需要盯着栈顶。栈顶如果不满足条件说明位于它下面的元素更不可能满足因为单调性的关系值要么更大要么更小位置也更远。这种“只看栈顶”的做法正是性能提升的核心。2.4 复杂度背后的不变式每个元素入栈一次出栈最多一次。虽然 while 循环可能一次性弹出多个元素但所有弹出的总数不超过 n - 1所以总迭代次数是线性的。很多初学者担心 while 嵌套 for 会不会变成 O(n^2)其实不会因为每个元素不会“被弹第二次”。这个不变式很重要面试问复杂度的时候可以直接答。3. 统一模板与记忆方法3.1 一个函数收掉四种情况我最终用到的 Python 模板长这样def monotone_stack(nums, directionright, targetgreater): n len(nums) res [-1] * n stack [] indexes range(n) if direction right else range(n - 1, -1, -1) for i in indexes: if target greater: while stack and nums[stack[-1]] nums[i]: res[stack.pop()] i else: # smaller while stack and nums[stack[-1]] nums[i]: res[stack.pop()] i stack.append(i) return res调用方式nums [3, 1, 4, 2] # 右侧第一个更大的下标 print(monotone_stack(nums, right, greater)) # [2, 2, -1, -1] # 右侧第一个更小的下标 print(monotone_stack(nums, right, smaller)) # [1, -1, 3, -1] # 左侧第一个更大的下标 print(monotone_stack(nums, left, greater)) # [-1, 0, -1, 2] # 左侧第一个更小的下标 print(monotone_stack(nums, left, smaller)) # [-1, -1, 1, 1]手动验一下“左侧第一个更大”索引 1 的值 1左边第一个比它大的是索引 0 的值 3所以返回 0索引 3 的值 2左边第一个比它大的是索引 2 的值 4所以返回 2。输出完全正确。这个模板的核心思路是当我在某个方向遍历时遍历到的元素会“推动”栈里的旧元素找出答案。方向决定最终res数组存储的是哪一侧的结果target决定触发条件是比较“更大”还是“更小”。3.2 怎么写不会错我给自己总结了一套写代码的顺序每次直接按这个顺序来先定方向需要“右侧”就在从左到右的 range 上遍历需要“左侧”就在 reversed range 上遍历。再定触发需要“更大”就写nums[stack[-1]] nums[i]需要“更小”就写nums[stack[-1]] nums[i]。弹栈赋值res[stack.pop()] i这一步处理的是“被弹出元素的答案”。最后入栈stack.append(i)。还有一个快速自查的土办法拿[1, 2, 3]这个最简单的数组测试。右侧第一个更大的正确结果是[1, 2, -1]如果返回[2, -1, -1]之类的八成是方向搞反了。拿[3, 2, 1]测右侧第一个更小正确结果是[1, 2, -1]也可以顺手验证。3.3 入栈前看栈顶求当前元素那一侧的答案上面的模板解决的是“每个元素作为等待者出栈时得到答案”。但有另一类问题问的是“当前元素的某侧边界”这时可以在入栈前先清栈然后直接读栈顶。例如求“每个元素左侧第一个比它小的位置”def left_smaller(nums): n len(nums) res [-1] * n stack [] for i in range(n): while stack and nums[stack[-1]] nums[i]: stack.pop() res[i] stack[-1] if stack else -1 stack.append(i) return res这段代码从左往右扫描弹出所有不小于当前值的元素剩下的栈顶就是左边第一个比当前值小的位置。它和通解模板的区别在于一个给“旧元素”写答案一个给“当前元素”写答案。实际上它们是同一个单调栈思想的镜像版本在求最大矩形这类需要同时算左右边界的题目里两种写法经常搭配使用。4. 实战变形从温度统计到柱状图矩形的完整套用4.1 温度问题右侧第一个更高的距离一个很经典的实际场景是这样给一个数组记录每天的天气温度要输出一个等长数组每位表示“还需要等几天才能遇到更高温度”没有则填 0。输入[30, 34, 32, 35, 30]正确答案是[1, 2, 1, 0, 0]。和通解模板相比这里只改一个地方出栈时记录的不是下标而是下标差。def daily_temperatures(temps): n len(temps) ans [0] * n stack [] for i in range(n): while stack and temps[stack[-1]] temps[i]: prev stack.pop() ans[prev] i - prev stack.append(i) return ans从左到右手动跑一遍i1 时 34 30弹出 0ans[0] 1i3 时 35 依次弹出 32 和 34ans[2] 1ans[1] 2。最后栈里剩 35 和 30 对应的位置它们后面没有更高温度保持 0。逻辑和通解完全一致只是结果从“找到答案的下标”变成了“找到答案的距离”。4.2 柱状图最大矩形左右边界都要找给一排柱子高度求最大矩形面积。典型输入[2, 1, 5, 6, 2, 3]最大面积是 10。这个问题的核心思路是以每根柱子的高度作为矩形高度求出它能向左右延伸的最大宽度。换句话说每根柱子需要知道“左边第一个比它矮的位置”和“右边第一个比它矮的位置”。def largest_rectangle_area(heights): n len(heights) left [-1] * n stack [] for i in range(n): while stack and heights[stack[-1]] heights[i]: stack.pop() left[i] stack[-1] if stack else -1 stack.append(i) right [n] * n stack [] for i in range(n - 1, -1, -1): while stack and heights[stack[-1]] heights[i]: stack.pop() right[i] stack[-1] if stack else n stack.append(i) ans 0 for i in range(n): area heights[i] * (right[i] - left[i] - 1) ans max(ans, area) return ans这里有个细节会影响正确性相等高度的柱子怎么处理。如果左右都找“严格小于”那么多个相等柱子会互相干扰导致同一高度的矩形被重复计算或者漏算。我的做法是左边弹掉的右边弹掉的也就是一侧用“小于等于”作为边界另一侧用“严格小于”作为边界。这样每个等高的柱子被划分给唯一的方向结果不重不漏。4.3 接雨水容易混淆的另一个栈用法接雨水问题经常被和“找第一个更高元素”混为一谈但它其实不是“第一个”而是要找到左右两边能存水的墙。这个场景下单调栈的写法是维护一个递减栈每遇到一个比栈顶高的新元素就说明栈顶位置出现了凹槽然后取栈中下一个元素作为左墙新元素作为右墙。def trap(heights): stack [] ans 0 for i, h in enumerate(heights): while stack and heights[stack[-1]] h: bottom heights[stack.pop()] if not stack: break left stack[-1] width i - left - 1 height min(heights[left], h) - bottom ans width * height stack.append(i) return ans我建议把接雨水当成“单调栈的另一个模型”单独记而不是强行塞进前面的通解。通解处理的是“每个位置的第一个更大/更小元素”接雨水处理的是“凹槽的面积”。虽然都用单调栈但语义不一样混着记最容易翻车。4.4 所有子数组最小值之和通解的高频变形还有一个高频题是求数组中所有连续子数组的最小值之和。直接枚举所有子数组是 O(n^2)肯定不行。单调栈的解法是对于每个位置 i计算有多少个子数组以arr[i]作为最小值再累加arr[i] * 数量。关键在于以arr[i]为最小值的子数组范围左边界是“左边第一个比它小的位置 L”右边界是“右边第一个比它小的位置 R”。在区间(L, R)内任意一个包含 i 的子数组的最小值都是arr[i]数量是(i - L) * (R - i)。def sum_subarray_mins(arr): n len(arr) left [-1] * n stack [] for i in range(n): while stack and arr[stack[-1]] arr[i]: stack.pop() left[i] stack[-1] if stack else -1 stack.append(i) right [n] * n stack [] for i in range(n - 1, -1, -1): while stack and arr[stack[-1]] arr[i]: stack.pop() right[i] stack[-1] if stack else n stack.append(i) ans 0 MOD 10**9 7 for i in range(n): ans (ans arr[i] * (i - left[i]) * (right[i] - i)) % MOD return ans这里同样要小心重复元素。如果左右都找严格小于遇到[2, 2, 2]时三个位置都会把自己的子数组当成“最小值位置”产生重复统计。处理方式是左边界弹掉严格大于当前值的元素右边界弹掉大于等于当前值的元素这样每个相等值的归属是唯一的。5. 常见报错与踩坑实录5.1 相等元素把结果污染我见过最多的错误就是把和写反。本文前面也提到过“右侧第一个更大”必须是严格大于相等不应该触发弹出。如果在找严格更大时写成那么[2, 2, 3]中第一个 2 会被第二个 2 弹出并把第二个 2 当成它的答案这显然是错的。这种错误不容易从结果直接看出来因为偶尔数组里没有相邻相等值时输出可能恰好正常。我建议调试时打印每次弹出时的栈顶、当前下标和值一旦看到两个相等的值互相触发基本就是比较符号的问题。5.2 栈为空时的取值while 循环结束后如果看到res[i] stack[-1]就直接写碰到栈为空会立刻报错。尤其在计算左边界时如果元素左边没有更小的值栈就是空的。我习惯这样写if stack: res[i] stack[-1] else: res[i] -1当然也可以维护一个哨兵元素在栈底放一个特殊索引省去判断。但我觉得这个优化收益不大反而增加了理解成本新手阶段老老实实写判断更安全。5.3 方向搞反的现场有一次我在模拟项目X里写一个区间统计模块想求每个位置的“左侧第一个更小值”。代码写完以后样例输出却全变成了“右侧第一个更小”的结果。排查了很久最后发现是函数里默认参数写成了directionright而真正调用时并没有覆盖这个默认值。那次之后我就养成一个习惯在求左侧答案的函数入口加一行注释说明“本函数从右往左遍历返回的是左侧结果”同时默认参数留空强制调用方显式传入方向。这个习惯帮我避免了很多方向混淆。5.4 返回值初始值的选择通解模板里没有答案的位置默认返回 -1但这并不是所有场景都合适。比如最大矩形问题里右边界默认值应该设成数组长度 n左边界默认值设成 -1这样宽度公式right - left - 1可以直接用不需要额外特判。换句话说初始值并不是随手填的而是业务语义的一部分。写代码前先想清楚这个题目里“没有答案”到底应该表示什么是 -1、是 n、还是 0想清楚之后再写边界判断会少很多。5.5 调试视角把栈底到栈顶打印出来我本地调试栈问题时会写一个辅助函数把当前栈内容按栈底到栈顶打印出来连同对应位置的值一起看def debug_stack(stack, nums, current_idx): print(fi{current_idx}, stack{stack}, stack_values{[nums[x] for x in stack]})每次入栈和出栈后都调用一下。数据量比较小的时候盯着打印出来的单调性变化找原因比盯着代码发呆快得多。还有一个小经验弹栈的逻辑一定用while不要用if。如果发现只弹了一个元素就停了多半是条件没写好。5.6 复杂度再确认一遍最后把复杂度钉死每个下标最多入栈一次、出栈一次while 循环的总迭代次数不会超过 n所以即使写法上看起来像双层循环实际时间复杂度是 O(n)空间复杂度 O(n)。面试被问到时就说“每个元素最多进栈一次、出栈一次弹栈总次数有上界”这句话就够了。我自己最早也是把左边大、右边小、左边小、右边大当成四种题型分别背后来才意识到它们只是同一个单调栈模板的四种参数组合。现在每遇到这类题只需要先确认两个问题要找哪一侧的答案是严格大小还是可以相等然后直接套模板。如果你也经常在这种题上栽跟头建议把打印栈的调试习惯练起来遇到边界问题会轻松很多。最后再分享一个小技巧写完代码后拿一个长度三的全递增数组和一个全递减数组各测一遍左右方向对不对立刻就能看出来这个土办法比在脑子里空想要可靠很多。