刷算法题的时候单调栈是我最早觉得“有点玄”的数据结构之一。明明只是一条普通的栈加上“单调”两个字就突然能解决一批看起来必须暴力枚举的题目。最典型的就是LeetCode 739“每日温度”给你一个温度数组要求每个元素往后第一个温度更高的日子还要等几天。直接两层循环当然能做但数据规模到10^5就麻了。单调栈呢一趟扫完时间O(n)代码二十行以内。这篇文章不打算只是贴模板我想把单调栈背后的直觉、两套形态、经典题目和踩坑过程全部拆开讲。如果你正在刷LeetCode、准备算法面试或者看过几篇单调栈文章但总觉得没吃透希望这篇能帮你把这一块真正焊死。1. 单调栈在解决什么类型的问题1.1 缺少单调栈时暴力枚举的代价先回到“每日温度”这道题。题意很简单给定列表 temperatures返回一个数组 answer其中 answer[i] 表示在第 i 天之后需要等待多少天才会出现更高温度如果之后都没有更高温度则填0。最常见的写法是两层循环外层固定第 i 天内层从 i1 一直往后找找到第一个比当前温度高的位置记录下标差。代码很简单我敢说绝大多数人第一次刷到它就是这种解法。但暴力枚举的问题也很明显内层循环在最坏情况下要反复扫描整体复杂度是 O(n^2)。如果 n 是 10^5就需要大约 10^10 次比较在多数在线评测环境里几秒内跑不完更别提实际业务里的性能要求。很多人做算法题一直停留在暴力层不是因为不知道“可以优化”而是没有一种工具能把“查找右侧第一个更大的数”这类操作从 O(n) 单次降到均摊 O(1) 总耗时。单调栈就是为这个大场景量身定做的。1.2 单调栈的直觉就像排队时只记住比自己高的个子单调栈最核心的直觉我一般用排队场景来理解。想象你是队伍中某个位置的等待者你要找的是“身后第一个比你高的人”。如果从左到右依次看过去当一个高个子出现时前面所有比他矮的、还在等待的人都能在这一刻“结清答案”——他们的下一个更高的人就是眼前这个高个子。而那些比高个子还高或和他一样高的人无论如何都轮不到眼前这个人来结清所以会继续留在候选池里等待。单调栈就是把这个候选池用栈来组织并且让栈内元素按某个单调方向排列。当新来的元素破坏了这个单调性时就不断弹出栈顶元素为它们“结清答案”直到重新满足单调性再把新元素压入栈。这样一来每个元素最多被压入一次、弹出一次整体代价就是线性的非常干净。2. 单调栈原理拆解两种形态和两套模板2.1 单调递增栈和单调递减栈怎么选很多人第一关就卡在这里到底什么时候用单调递增栈什么时候用单调递减栈我的记忆方式很简单——看你要找的目标方向。如果你要找“右侧第一个更大的元素”栈内元素要保持从栈底到栈顶递减。为什么因为只有当新元素比栈顶元素更大时栈顶才有机会结清答案如果新元素比栈顶小或相等说明它“不构成挑战”应该压栈等待后续更大的元素。反过来如果你要找“右侧第一个更小的元素”栈内元素就要从栈底到栈顶递增因为你需要遇到更小的元素来触发弹出结算。下面这张表我建议直接记在笔记里目标栈的方向从底到顶弹出触发条件代表问题右侧第一个更大的元素递减当前元素 栈顶每日温度、下一个更大元素右侧第一个更小的元素递增当前元素 栈顶柱状图中最大的矩形左侧第一个更小的元素递增当前元素 栈顶柱状图边界、接雨水注意这里的“递增”“递减”一定要定义清楚我指的是从栈底到栈顶的方向。不同资料说法可能相反做题前先把定义统一能避免很多混乱。2.2 找右侧第一个更大元素的通用模板以“找右侧第一个更大元素”为例标准模板我习惯写成这样栈里存下标Python 代码如下def solve(nums): n len(nums) ans [-1] * n stack [] # 栈底到栈顶递减存下标 for i, x in enumerate(nums): while stack and x nums[stack[-1]]: idx stack.pop() ans[idx] i # 或者依据题目需求记录具体值 stack.append(i) return ans这里有个关键点为什么栈里要存下标而不是直接存值因为很多题目最终要求返回“下标距离”或“天数差”只有下标才能直接算距离。同时只要有下标通过 nums[stack[-1]] 随时都能拿到对应的值信息一点也没丢。所以我的建议是无脑存下标这是最通用的写法。另一个容易忽略的操作顺序先 while 弹出结算再把当前元素入栈。千万不能反过来。如果先把当前元素入栈栈顶就是它自己后续比较会误判甚至死循环。2.3 找相邻更小边界另一类单调栈应用找“右侧第一个更大元素”只是单调栈的一面另一面同样重要找某元素的左边和右边分别离它最近、比它小的元素。这种场景在“柱状图中最大的矩形”和“接雨水”里极其常见。做法是维护一个从栈底到栈顶递增的栈。当新元素比栈顶元素小时说明栈顶元素的“右侧第一个更小元素”就是当前元素弹出栈顶后新的栈顶元素如果存在就是那个被弹出元素的“左侧第一个更小元素”。通过这两条边界之间的距离就能算出以该元素为高/基准的可扩展宽度。很多初学者只知道“单调栈能找下一个更大”却不知道它还能找左右两侧的小边界导致柱状图矩形的题怎么也做不出来。其实是模板的镜像玩法本质没有变。2.4 为什么时间复杂度是O(n)关于复杂度我想多解释几句因为面试时经常会被问。在单调栈的整个运行过程中每个元素只会被压入栈一次。至于弹出看似 while 循环会弹很多次但每次弹出一个元素都代表那个元素永远不会再回到栈里。所以所有 while 循环累计弹出的总次数是 O(n)——每个元素最多被弹出一次。加上一层 for 循环本身也是 O(n)整体就是 O(n) 时间额外空间是栈的开销 O(n)。这个“均摊”思想很重要。它不像二分那样严格每次操作都是 O(log n)而是把总操作次数摊到 n 次遍历上每次平均 O(1)。刷题解释复杂度时说“每个元素入栈一次、出栈一次”是最稳妥的答案。3. 经典题目实操四道题带你彻底掌握单调栈3.1 每日温度LeetCode 739先说最经典的每日温度。给定 temperatures [73, 74, 75, 71, 69, 72, 76, 73]我们期望返回 [1, 1, 4, 2, 1, 1, 0, 0]。我平时面试新人时喜欢要求对方把整个栈变化过程当场手推一遍推完基本就知道是不是真懂了。我用下标和值一起走一遍i0温度73栈空直接入栈栈内 [0]。i1温度7474 栈顶73弹出下标0ans[0] 1 - 0 1然后1入栈栈内 [1]。i2温度7575 74弹出下标1ans[1] 12入栈栈内 [2]。i3温度7171 75不弹出3入栈栈内 [2,3]。i4温度6969 714入栈栈内 [2,3,4]。i5温度7272 69弹出下标4ans[4] 172 71弹出下标3ans[3] 5 - 3 2此时栈顶是下标27572 75停止弹出5入栈栈内 [2,5]。i6温度7676 72弹出下标5ans[5] 176 75弹出下标2ans[2] 6 - 2 46入栈栈内 [6]。i7温度7373 767入栈栈内 [6,7]。最终结果就是 [1,1,4,2,1,1,0,0]。注意下标6和7都没有被任何更大的温度顶出所以它们保持默认值0。这个手动推演的过程我强烈建议每个人自己写一遍比自己看十篇博客都管用。代码和模板几乎一一对应def dailyTemperatures(temperatures): n len(temperatures) ans [0] * n stack [] for i in range(n): while stack and temperatures[i] temperatures[stack[-1]]: idx stack.pop() ans[idx] i - idx stack.append(i) return ans3.2 下一个更大元素与环形数组LeetCode 496 / 503下一道是“下一个更大元素 I”。题目给两个数组 nums1 和 nums2nums1 是 nums2 的子集要求返回 nums1 中每个数在 nums2 里右侧第一个比它大的数的值没有就是 -1。这道题最直接的做法是先用单调栈把 nums2 中每个元素的“下一个更大元素”全部算出来存进哈希表然后遍历 nums1 按表取结果。为什么这样做合理因为 nums2 本身是结构源nums1 只负责查询如果把查询也做一遍暴力循环那复杂度又升回去了。用一个字典把单调栈结果记录下来查询就是 O(1)总复杂度 O(len(nums1)len(nums2))。写出来是这样def nextGreaterElement(nums1, nums2): nxt {} stack [] for x in nums2: while stack and x stack[-1]: nxt[stack.pop()] x stack.append(x) for x in stack: nxt[x] -1 return [nxt[x] for x in nums1]这道题因为是按“值”查询栈里直接存值没有问题。但如果你习惯存下标也完全可以用 nums2[stack[-1]] 做比较最后把值填进字典。两种写法各有舒适区我的建议是先用下标版本练熟理解本质后再自由切换。接下来的“下一个更大元素 II”是同一个命题但数组变成了环形也就是最后一个元素的下一个更大元素可以绕回数组开头找。处理环形数组有一个通用技巧把数组“逻辑拉长”成两倍长度遍历 i 从 0 到 2n-1用 i % n 取实际下标。单调栈照常工作。def nextGreaterElements(nums): n len(nums) ans [-1] * n stack [] for i in range(2 * n): idx i % n while stack and nums[idx] nums[stack[-1]]: ans[stack.pop()] nums[idx] if i n: stack.append(i) return ans这里有个小细节值得提醒入栈操作只在前 n 次循环进行后面的循环只负责“继续比较剩余元素”这样能避免同一个下标反复入栈逻辑更清爽。栈中最终留下的元素自然是找不到更大元素的答案保持 -1 即可。3.3 接雨水LeetCode 42接雨水是单调栈里难度明显上一个台阶的题因为它是用单调递减栈来“结算凹槽”的。height [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]要求计算这排柱子能接多少雨水。用单调栈时栈底到栈顶按柱子高度递减栈里存下标。当新柱子高度大于栈顶高度时说明当前栈顶柱子它自己处于一个凹槽底部的位置——它左侧有栈内比它高的柱子作为左墙右侧有当前柱子作为右墙。这个凹槽能接的水量由左右两侧中较矮的一侧减去凹槽底的高度决定宽度则是两侧下标之差再减1。Python 代码如下def trap(height): n len(height) ans 0 stack [] for i in range(n): while stack and height[i] height[stack[-1]]: bottom stack.pop() if not stack: break left stack[-1] width i - left - 1 h min(height[left], height[i]) - height[bottom] ans width * h stack.append(i) return ans注意到一个关键边界当弹出栈顶后栈已经为空说明左侧没有能挡住水的墙凹槽不成立直接 break 跳出 while。这个坑非常隐蔽我第一次写的时候漏了结果把左边没有墙的情况也拿来算水量答案错得离谱。我建议把接雨水和每日温度放在一起对比每日温度是“遇到更大的就结算高度位置”接雨水是“遇到更大的就结算水量面积”。模板骨架一样差别在于弹出时需要多看一层——凹槽的底是当前弹出来的栈顶左墙是弹出后的栈顶元素。3.4 柱状图中最大的矩形LeetCode 84柱状图中最大的矩形是另一道“劝退题”它表面上是求面积本质上是找每个柱子左右两侧第一个比它矮的位置从而确定以它为高度的最大可扩展宽度。经典例子 heights [2, 1, 5, 6, 2, 3]。以高度5的柱子为例它的左侧第一个比它矮的是下标1高度1右侧第一个比它矮的是下标4高度2所以高度5能扩展的宽度是4-1-12能形成的矩形面积就是 5 * 2 10。这个答案也是全体柱子中的最大面积。用单调递增栈处理时遇到新柱子比栈顶柱子矮栈顶柱子的“左右边界”就都确定了可以立刻结算面积。为了处理最后栈里剩余的递增柱子我会在原数组末尾补一个高度0的哨兵让它把栈里所有柱子强制弹出逻辑非常干净。def largestRectangleArea(heights): heights.append(0) ans 0 stack [] for i in range(len(heights)): while stack and heights[i] heights[stack[-1]]: h heights[stack.pop()] left stack[-1] if stack else -1 width i - left - 1 ans max(ans, h * width) stack.append(i) return ans注意边界处理弹出后栈为空说明当前柱子左边没有任何比它矮的柱子那 left 就是 -1宽度就是当前下标到左边虚拟边界之间的范围也就是 i。用 i - (-1) - 1 i正好正确。这个公式想清楚一次之后写任何单调栈变体都不会乱。为什么这题要用单调递增栈因为要“遇到更矮的柱子时结算当前柱子”的矩形只有栈底到栈顶递增才能保证栈内每个元素左侧的元素都比它矮当前新元素比栈顶矮时栈顶的右侧边界也出现了。两个边界同步确定结算自然成立。3.5 移除k位数字LeetCode 402单调栈的贪心变体除了“找边界”单调栈还能和贪心结合。移除k位数字这题要求从数字字符串中移除 k 位使剩余数字组成的数尽可能小。直观策略是从左到右扫描如果当前数字比前面保留的数字还小那就应该把前面那个较大的数字删掉因为把高位较大的数换成低位较小的数整个数字会变小。这个过程天然就是单调栈——维护一个从栈底到栈顶递增的栈遇到更小的数字时弹出栈顶每弹一次相当于删除一位直到 k 次用完。def removeKdigits(num, k): stack [] for ch in num: while k 0 and stack and ch stack[-1]: stack.pop() k - 1 stack.append(ch) while k 0: stack.pop() k - 1 while stack and stack[0] 0: stack.pop(0) return .join(stack) if stack else 0这段代码有一个小毛病stack.pop(0) 是 O(n) 操作放在大样例上不够优雅。更稳妥的做法是用“指针列表”或最后统一 lstrip(0) 处理前导零。我写在这里只是因为它更能直观看懂逻辑。面试时如果写到这里建议顺手优化一下比如用拼接结果时跳过前导0或者在最后用循环统计前导零的个数再切片这样能给面试官留一个“复杂度意识很强”的印象。这道题已经不在“下一个更大元素”的范畴了但它仍然是单调栈思维你想维护一个单调序列破坏单调的部分就要被删除或调整。这类题做多了你会慢慢感觉到单调栈不是一个孤立的模板而是一种利用“历史候选顺序”来消除无效比较的手段。4. 单调栈常见误区与调试经验4.1 相等元素的处理原则我见过太多人栽在相等元素的处理上。以“下一个更大元素”为例题目要求严格大于才算是“更大”所以 while 里必须写大于不能写大于等于。如果写成大于等于相等元素会被提前弹出结算得到错误答案。比如每日温度数据 [76, 76, 73, 80]第一个76本应在遇到80时得到答案3但如果相等也弹出它会在第二个76处提前结算成1自然就错了。反之如果你自己设计题目时想找“下一个大于等于”那就要把比较符号改成 。做题前先确认题目要求是“严格大于”还是“大于等于”这是最省时间的习惯。4.2 栈里存值还是存下标有些题答案要求返回“值”比如下一个更大元素 I栈里直接存值写起来简单。有些题要求返回“距离”比如每日温度则必须存下标。如果搞混算距离时只能靠数组 indexOf 之类的操作复杂度就退化了。我的统一习惯是一律先存下标。下标可以同时获得值和位置是最通用的编码。等熟练以后再针对值类问题优化成存值。面试手写代码时建议先和面试官确认一句“我存下标需要取值时用数组访问”既展示思路又避免歧义。4.3 栈空与边界条件的处理单调栈代码最容易崩的位置就是 while pop 之后栈为空。接雨水里pop 后栈空表示左边没有墙需要 break不然会拿一个不存在的 left 去算宽度。柱状图最大矩形里pop 后栈空说明 left 取 -1用虚拟边界来算宽度。这两处的“栈空”含义完全不同但核心逻辑都是统一的先判断栈是否为空再决定 left 的取值。我在代码里习惯用left stack[-1] if stack else -1一行解决简单可靠。另一个容易忽略的边界是遍历结束后栈里还会剩下一些元素。它们可能是找不到更大元素而保持默认答案的元素也可能需要在最后结算。柱状图的最大矩形就是靠哨兵0保证最后结算而每日温度不需要额外处理因为答案默认就是0。不同题目遍历结束后栈的状态不同处理方式也不同——拿到题目先想清楚“最终栈里的元素还欠不欠答案”。4.4 手写模拟两遍比看十遍博客有效我说句掏心窝的话单调栈看再多文章都不如自己手动模拟一遍来得实在。我第一次学的时候也是看了很多博客自认为懂了结果写接雨水时连续交了三版错误的代码。后来老老实实把每日温度和接雨水的完整栈变化用纸笔画了一遍标出每一步的 i、栈内下标、对应数值、弹出动作、结算结果。画完之后脑子里对“什么是左边界、什么时候结算、为什么栈空要break”才有了真正的画面感。我还有一个具体的调试技巧在 while 循环里临时打印print(i, stack, ans)观察每次弹出的前后状态对比手推结果。尤其适合单调栈这种“状态被压着”的数据结构局部错误很难一眼看出来打印是最直接的定位工具。5. 面试实战建议从识别题目到写出模板5.1 该怎么判断题目能用单调栈面试时判断一道题是否适合用单调栈可以从关键词入手。只要题目中出现“右边第一个比它大的数”“左边第一个比它小的数”“下一个更大/更小元素”“环形数组中寻找下一个更大元素”基本上就可以把单调栈放到候选方案的第一位。还有一些题表面看不出“下一个”的关系但本质也是在找左右边界比如柱状图最大矩形、接雨水、最大宽度坡等。这类题通常涉及“以当前位置为基准向两侧扩展直到遇到某个限制条件”暴力做是 O(n^2)如果想优化到 O(n)就试试把限制条件建模成“第一个更小/更大的元素”。我在面试中考察候选人时如果对方能说出“这题我需要每个元素左右两侧第一个更小边界所以用单调递增栈”我基本就会认为他对这个知识点有体系化的理解如果只能背出每日温度的模板遇到变体就容易卡壳。5.2 模板的四步记忆法把单调栈代码浓缩成一个四步口诀我自己面试前也会在心里过一遍第一步确认方向根据目标是“更大”还是“更小”决定用递增栈还是递减栈第二步栈存下标统一用 nums 数组取值第三步while 循环当前元素与栈顶比较触发结算条件就 pop 并处理答案第四步把当前元素下标入栈继续下一轮。这四步不是死板的但能有效防止漏写关键动作。我最常看到的新手错误就是只写了 while 和 pop忘了入栈或者入栈时存了值导致后面算不了距离。四步走一遍基本能消灭这类低级错误。还有一个小技巧如果不确定代码写得对不对可以先拿一个长度为3或4的例子手推一遍结果再对照代码脑内执行。这个习惯比急着提交节省太多时间。5.3 单调栈的扩展方向单调栈学完之后还可以往几个方向走。第一个是单调队列。单调栈处理的是“维护历史最优候选”而单调队列经常用于滑动窗口问题比如“滑动窗口最大值”。两者的关系很像双胞胎栈弹栈顶队列弹队头栈解决右侧/左侧最近关系队列解决滑动窗口范围内的极值问题。会了单调栈再去学单调队列会顺很多。第二个是和其他算法配合。比如前缀和处理后的子数组问题、结合哈希表加速的变体、与贪心策略结合的删除类问题等。单调栈往往不是单独出现而是作为整体思维的一个环节。第三个是模板的语言迁移。虽然我用 Python 讲但 C 里无非是vectorint st; while (!st.empty() nums[i] nums[st.back()])这样的写法Java 则是DequeInteger stack new ArrayDeque();。思路完全一致语言只是皮相。最后聊一点我的个人体会刷单调栈这段时间我最大的感受是这个结构解决的不是“某个单独问题”而是一类“靠顺序比较就能消除冗余”的问题。它和我最早接触的暴力枚举差距非常大——暴力依赖“每个都查一遍”单调栈依赖“只要前面的矮个子被高个子覆盖就再也不用回头看它们”。面试官喜欢这类题也是因为简单背后有推理边界里藏着细节。如果你刚开始学别急着背题先动手画两次栈变化把比较方向、存值还是存下标、栈空怎么处理这三个问题想清楚。等你形成肌肉记忆之后每日温度、接雨水、柱状图这类题就不再是背答案而是每次都能快速写出来的基本功了。