刷题刷到第50天遇到的第一个让人“卡住”的经典数据结构就是单调栈。相比之前学的普通栈、队列单调栈看起来只是多了一个“单调”的约束条件但它在解决“找下一个更大/更小元素”、“计算最大矩形面积”、“接雨水”这类问题上能把暴力解法的 O(n²) 时间复杂度直接降到 O(n)。很多人在这一步栽跟头不是因为不理解栈的先进后出而是不清楚单调栈到底在维护什么信息、什么时候该弹出。这篇博客不打算铺开讲全套算法笔记而是从我刷题、总结错题的实际经验出发拆解单调栈的核心原理、两类栈的选择逻辑、五道经典题型的完整推导以及那些你在题解里看不到的边界陷阱。不管你是刚开始刷算法的初学者还是已经刷了几百题想巩固基础的老手这篇内容都能帮你在10分钟内把单调栈这条线彻底吃透。1. 单调栈到底是什么从一道面试题说起1.1 暴力解法为什么不行先看一道最经典的题目给定一个整数数组找到每个元素右边第一个比它大的元素。很多人第一反应就是双重循环外层遍历每个元素内层从当前位置往后找第一个更大的元素。这个思路完全正确但时间复杂度是 O(n²)。当数组长度达到 10^5 甚至 10^6 时跑一次就要 10^10 次操作在绝大多数在线评测系统里都会超时。我一开始也不太理解为什么需要引入一个新数据结构。直到我手动模拟了几组数据才发现暴力解法最大的问题在于“重复比较”。比如数组是 [1, 3, 2, 4]找元素 1 右边第一个更大元素时比较了 3 之后发现答案就是 3马上停止了。但找元素 2 时又从头开始比较。这些比较操作之间没有任何信息可以复用导致同一个数字被反复扫描。单调栈的核心价值就在于“一次遍历信息留存”。它用一个栈把已经扫描过但还没找到答案的元素保存下来当遇到一个新的元素时通过比较栈顶元素和新元素的大小关系一次性把能确定答案的元素全部弹出并记录答案。每个元素最多入栈一次、出栈一次所以总时间复杂度是 O(n)。1.2 单调栈到底在维护什么单调栈本质上是在维护一个“潜在候选集”。从栈底到栈顶元素按照某种单调顺序排列——要么单调递增要么单调递减。这个单调性不是随便规定的它直接决定了你解决的是“右边第一个更大”还是“右边第一个更小”的问题。拿“找右边第一个更大元素”来说我们需要维护一个从栈底到栈顶单调递减的栈。为什么因为当你从左到右遍历数组时假设栈顶元素是当前已经扫描过的元素中“最有可能被下一个更大元素影响”的那个。新元素如果比栈顶大说明栈顶元素右边的第一个更大元素就是它此时弹出栈顶继续看新的栈顶直到栈顶元素比新元素大或者栈为空。这时的栈仍然是单调递减的。很多初学者会混淆递增栈和递减栈的选择。我的记忆方式是目标是“找更大”就用递减栈栈内从底到顶递减目标是“找更小”就用递增栈。这个规律虽然不能覆盖所有题型但对90%以上的经典题目都适用。后面我会详细解释为什么以及什么时候这个规律会被打破。2. 单调栈的模板与两类栈的选择2.1 单调递增栈和单调递减栈怎么分单调栈分两种单调递增栈和单调递减栈。这里要注意描述的是“从栈底到栈顶”的顺序。单调递增栈就是栈底最小、栈顶最大新元素入栈时会把所有比它小的元素弹出单调递减栈则相反栈底最大、栈顶最小新元素入栈时会把所有比它大的元素弹出。选择哪种栈核心就看你在弹出元素时想确定什么答案。用“下一个更大元素”举例当你遇到一个比栈顶大的新元素时这个新元素就是栈顶元素“右边第一个更大值”所以你需要在弹出栈顶时记录答案。想要触发这种弹出新元素必须大于正在比较的栈顶元素从而低的先被弹出留下的较高的留在栈底这就是一个递减栈。如果目标是“右边第一个更小元素”思路完全对称新元素比栈顶小的时候栈顶的答案就是新元素于是弹出栈顶最终元素从栈底到栈顶呈递增排列。掌握这个对称性后你就不需要死记硬背题目对应的栈类型而是根据“何时弹出、弹出时记录什么”来现场推导。2.2 两套模板代码我整理了两套最精简的模板一套用数组下标作为栈元素另一套直接用数值。数组下标版本更通用因为有时候我们需要的不是“更大值本身”而是“更大的那个元素和当前元素之间的距离”这时候必须用下标。### 找右边第一个更大元素单调递减栈 def nextGreaterElements(nums): n len(nums) res [-1] * n # 默认右边没有更大元素 stack [] # 存下标栈底到栈顶单调递减 for i in range(n): # 当新元素大于栈顶元素时栈顶的答案就是新元素 while stack and nums[i] nums[stack[-1]]: idx stack.pop() res[idx] nums[i] stack.append(i) return res### 找右边第一个更小元素单调递增栈 def nextSmallerElements(nums): n len(nums) res [-1] * n stack [] # 栈底到栈顶单调递增 for i in range(n): while stack and nums[i] nums[stack[-1]]: idx stack.pop() res[idx] nums[i] stack.append(i) return res模板就两行关键代码一个while循环负责弹出一个append负责入栈。区别只在于比较符号是“”还是“”。这也是为什么我强调理解触发条件比记住模板更重要——题目一变符号一换如果你不理解逻辑就只能靠死记硬背很容易在变形题上翻车。2.3 栈里存什么下标 vs 数值绝大部分情况下推荐存下标。原因有三个第一通过下标可以随时访问元素值存下标等于同时保存了“值”和“位置”两种信息第二求解距离类问题时比如每日温度、矩形宽度计算你必须要用下标相减第三当数组存在重复元素时存下标可以清楚地区分每个元素避免混淆。直接存数值的写法在简单题里看着方便但一旦遇到需要距离、面积、区间这类计算就不得不额外维护一个位置数组反而多此一举。我自己刚开始刷题时就喜欢存数值结果做“柱状图中最大矩形”这道题时怎么都算不对面积静态调试半天才发现是宽度没算对。换成存下标后问题迎刃而解。3. 经典题型逐题拆解从入门到变形3.1 每日温度最简单直观的入门题LeetCode 739题的每日温度是单调栈最经典的入门题目。题目给出一组每天的温度要求返回一个数组每个位置表示要等多少天才能等到更高的温度如果之后没有更高的温度就填0。比如温度是 [73, 74, 75, 71, 69, 72, 76, 73]输出 [1, 1, 4, 2, 1, 1, 0, 0]。这道题本质上就是“下一个更大元素”的距离版本。因为要求是“多少天后”所以栈里必须存下标。思路是维护一个递减栈遍历每一天的温度如果当前温度大于栈顶下标对应的温度说明栈顶那天的更高温度出现了答案就是当前下标减去栈顶下标一直弹出直到栈顶温度大于等于当前温度然后当前下标入栈。我第一次做这道题时犯了一个很低级的错误在弹出循环里用了一个“if”而不是“while”。结果只处理了栈顶一个元素后面的候选元素全部被留在栈里没有更新答案。后来我总结了一个检查方法只要弹出操作发生在循环里就问自己这个while需不需要继续处理多个元素——只要当前元素可能同时是多个元素的下一个更大值就必须用while。3.2 下一个更大元素处理环形数组和重复值“下一个更大元素”有几道变形题其中最有代表性的是下一个更大元素II——数组变成了环形数组。经典做法有三种复制数组拼成两倍长、取模遍历两轮、或者直接在遍历时对下标取模但不增加实际数组长度。最推荐取模的方式因为内存占用少代码也简洁。环形数组的处理核心在于为什么要遍历两遍因为是环形的某个元素的“下一个更大元素”可能绕回到它的前面。遍历一遍只能找到物理位置在右边的更大元素绕回的部分必须再走一遍才能覆盖。但这里有个陷阱如果第二遍重复弹出同一个元素会导致死循环或者错误答案所以通常配合一个计数器或者直接限制遍历次数为2n。下一道变形题是下一个更大元素I它给了两个数组nums1和nums2nums1是nums2的子集要求返回nums1中每个元素在nums2中对应位置右边的第一个更大值。这道题可以先对nums2整体跑一次单调栈把每个元素的下一个更大值存进哈希表然后遍历nums1直接查表。正因为栈里存的是下标你可以同时拿到值和索引把结果组织得非常清晰。3.3 柱状图中最大的矩形从“找更大”到“找更小”柱状图中最大的矩形是单调栈题里最难理解的一道但也是最能检验你是否真正掌握单调栈的题目。给定一组非负整数表示柱子的高度每个柱子的宽度都是1求这些柱子能勾勒出的最大矩形面积。这道题的关键转折点是枚举每个柱子作为矩形的高度时矩形的左右边界分别是“左边第一个小于该柱子的位置”和“右边第一个小于该柱子的位置”。也就是说你需要维护的是单调递增栈而不是递减栈。这正是我前面说的“找更小用递增栈”的对称体现。具体做法是从左到右遍历当当前柱子高度小于栈顶柱子高度时弹出栈顶以“栈顶柱子的高度”作为矩形高度以“当前下标减去新的栈顶下标再减1”作为矩形宽度计算面积并更新答案。遍历结束后栈中可能还有剩余元素需要再统一处理一遍因为它们的右边界是数组末端。我第一次做这道题时宽度计算一直出错。后来我把整个入栈和弹出的过程在纸上画了一遍才明白当弹出第i个柱子时栈中它下面的那个柱子的下标就是它左边第一个比它矮的柱子的下标当前下标就是它右边第一个比它矮的柱子的下标。两者之间的所有柱子高度都大于等于当前柱子所以矩形宽度就是这个区间长度。理解到这个层面代码就变成了一个自然的推导结果。3.4 接雨水单调栈技巧的集大成者接雨水题目给出一组高度数组每个宽度为1问下雨后能接多少水。这道题有很多解法双指针、动态规划、单调栈。单调栈是实现最优雅的一种因为它可以在一次遍历中同时处理“左侧边界”、“右侧边界”和“坑的底部”这三个信息。接雨水的思路是维护一个单调递减栈。遍历高度时如果当前高度大于栈顶高度说明出现了可以存水的“坑”。此时弹出栈顶元素作为坑底新的栈顶作为左边界当前高度作为右边界。水的高度是左右边界高度的较小值减去坑底高度宽度是左右边界下标距离减1。这里有一个很容易被忽略的细节右边界必须“高于”左边界才能形成封闭坑不一定。接雨水里弹出一次后左边界可能还是比右边界高也可能还是比右边界低。无论哪种情况当前这个坑底的水量都能正确计算。所以需要不断循环弹出直到栈顶高度大于等于当前高度才能把这个“右边界”确定为新的围栏。这正是单调栈的精髓——它不依赖全局的比较而是利用栈内已有的单调顺序逐步计算每个局部坑的容量。我记得自己第一次写完接雨水代码后测试用例过了但提交时有个极端用例总差一点。后来发现是因为我在循环弹出后没有把当前下标入栈导致后续元素无法利用当前的右边界。补上这行代码后整个逻辑就通了。做题时经常出现这种“少一行代码”导致全盘皆输的情况所以每一步都要想清楚栈里的元素到底代表什么。4. 实操过程与代码实现细节4.1 边界条件的处理单调栈代码看着短但边界条件处理不好照样会错。我总结出三个必须注意的边界空栈时不能访问栈顶、数组末尾的剩余元素要统一处理、所有元素相等时不能把相等元素弹出去。空栈判断while循环里必须先判断stack不为空再访问stack[-1]。很多初学者写代码时把顺序颠倒导致“list index out of range”错误。我习惯写成while stack and 比较条件利用Python的短路特性一石二鸟。末尾剩余元素遍历完整个数组后栈里剩下的元素说明它们右边没有满足条件的元素。在“下一个更大元素”中直接保持默认值在“柱状图最大矩形”中需要追加一个高度为0的虚拟柱子强制把所有元素弹出这样就不用单独写处理逻辑了。相等元素大多数题目要求“下一个更大”而不是“下一个大于等于”所以遇到相等元素时不要弹出栈顶。比如数组 [2, 2, 1]右边第一个比第一个2更大的是1吗显然不是是1右侧没有更大的所以第一个2的答案应该还是-1。如果你在遇到相等元素时弹出栈顶第一个2就会被误判成2这是非常经典的错误。4.2 虚拟哨兵节点的妙用在许多单调栈题目中往数组末尾追加一个“哨兵”能大幅度简化代码。比如柱状图中最大矩形在题解中常见写法是给原数组追加一个0再开始遍历。为什么要加0因为0是最小值栈里所有比0大的柱子都会在最后一轮循环里被强制弹出这样你就不需要在循环结束后单独写一个“处理剩余栈”的代码块。接雨水题目也可以这样处理吗不行。接雨水里追加0会让最后一轮把所有元素都弹出来但弹出的过程中可能错误计算水容量因为最后一个0高度没有任何右侧边界根本不能构成坑。所以千万不要把柱状图那套方案直接照搬到接雨水上。要不要加哨兵取决于这道题最后剩下的元素是否还有继续处理的价值。我自己的习惯是先不加哨兵把基础版写对再考虑用哨兵简化。因为如果一个新手第一次接触单调栈就用哨兵技巧理解不到它背后的动机很容易在变体题里误用。先学会完整写法再学简化写法知识才是立体的。4.3 复杂度分析与空间优化单调栈的时间复杂度是O(n)因为每个元素最多被压入一次、弹出一次。空间复杂度是O(n)最坏情况下所有元素严格单调递增或递减栈里会存下全部n个元素。在空间上有一个常见的进阶优化方向如果题目允许修改原数组可以把原数组本身当作栈来用。比如遇到“下一个更大元素”只要求返回结果数组不要求保留原数组时可以用一个指针模拟栈顶在原数组上覆盖写入。这样能省下额外的栈空间代码也更简洁。不过这种优化属于锦上添花面试时可以先写标准的栈方案再提一句可以优化给面试官展示你的进阶思考。还有一类问题是需要同时维护“左边第一个小于”和“右边第一个小于”两个信息。很多题解会写两次循环一次求左边界一次求右边界。实际上一次单调栈遍历就能同时确定这两个信息当元素被弹出时当前遍历位置就是右边界栈内剩下的下一个元素就是左边界。这也是“柱状图中最大的矩形”大多数高效解法的核心。5. 常见问题与排查技巧实录5.1 容易出错的三个经典case我在刷题过程中反复踩过几个坑整理出来供大家参考输入是空数组直接返回空结果。这种corner case最基础但最容易被忽略。很多初学者在写完主逻辑后不特意处理空数组结果一提交就报错。建议所有单调栈题目的第一行都写上空数组保护。所有元素都相同比如 [2, 2, 2, 2]。此时“下一个更大元素”没有解结果数组全部是-1“每日温度”结果全部是0“最大矩形面积”答案则是单个柱子的高度乘以1即2。如果你在代码里用了作为弹出条件这些题目的答案就会全部出错。数组是严格递减比如 [5, 4, 3, 2, 1]。找不到任何“右边更大元素”所有答案都是-1。但如果用严格递增的弹出条件你会把所有元素都弹出来这不是报错却会得到一个全错的答案。排查这类问题最好的办法就是自己手动模拟一次简短的递减序列。5.2 排查技巧用纸面模拟替代盲目调试单调栈代码的调试方法和普通代码很不一样。普通代码报错后可以打印日志、打断点但单调栈的状态变化非常快打印日志会输出大量中间信息反而容易看晕。我的经验是遇到错题先别急着打印拿一组小数据在纸上手动模拟一遍。手动模拟时写下三个东西当前遍历到的下标、当前栈内元素、当前已确定的答案数组。每进入一次while循环就在纸上划掉弹出的元素写上更新的答案。通常模拟不到10个元素你就能定位到是“弹出条件写反了”还是“答案更新的时机不对”。这个方法看起来原始但对于理解单调栈这种状态依赖型算法远比debugger高效。我还发现很多错误并不在栈操作本身而在“结果数组的默认值”。比如下一个更大元素的默认值应该是-1每日温度的默认值应该是0。如果你的默认值设错了哪怕栈的逻辑完全正确输出也是错的。所以我写单调栈题目时第一步永远是确认“没有满足条件的元素时答案应该填什么”。5.3 单调栈与单调队列的边界刷题时经常有人把单调栈和单调队列混淆。二者有本质区别单调栈只能在一端进行插入和弹出解决的是“寻找某个方向的第一个最值”单调队列是双端操作的队尾插入、队首删除通常用于滑动窗口问题比如求窗口内最大值或最小值。拿“滑动窗口最大值”那道题举例窗口每向右移动一位队首就要弹出不在窗口内的元素队尾要插入新元素并弹出所有比新元素更小或相等的元素。这样队首始终是窗口最大值。这个数据结构叫单调队列代码实现上用的是collections.deque而不是普通list。怎么判断一道题该用栈还是队列核心看“信息是否还需要保留”。单调栈留下的信息是为了等待右边未知的元素来匹配单调队列中窗口左边界移动时过期的元素必须被移除。如果题目是寻找左右固定边界内的最值一般用单调栈如果是一个滑动窗口不断平移优先考虑单调队列。这两个结构经常在综合大题的多个阶段配合出现区分清楚了解题思路会清晰很多。5.4 实战中总结出的三条经验第一先写框架再调符号。我刷到后面发现单调栈的代码框架就这么几行初始化结果数组、初始化栈、遍历数组、while弹出、更新答案、入栈。我每次做题都会先把这些行写出来再根据题目调整比较符号和答案更新逻辑。这比对着空白编辑器强行推导要快得多。第二正确理解“在弹出时记录答案”。单调栈最反直觉的地方是目标答案不是在新元素入栈时记录而是在旧元素被弹出时记录。很多初学者会习惯性在插入新元素时试图给新元素填答案那是暴力思维在作怪。新元素的答案要等下一个更大元素出现时才能确定所以在它自己被弹出时才能记录。第三不要过度崇拜单调栈。有些题目比如接雨水、最大矩形用单调栈很优雅但如果用双指针或者动态规划更好理解面试时选一个自己能讲清楚的方案更好。我见过很多候选人在白板上努力默写单调栈代码结果边界条件全错最终得分还不如用O(n²)但完全正确的暴力解。算法题的终极目标是解决问题而不只是秀数据结构。我个人在实际刷题中的体会是单调栈这个技巧本质上就是教你“延迟决策”。先让不确定答案的元素待在栈里等信息足够时再一次性结算。这个思想不仅在算法里通用在处理很多需要“等待后续信息”的业务场景时也很有启发。如果你刚开始学拿每日温度练手再挑战接雨水逐步感受栈里元素的“生命周期”。等你哪天看到一道题能下意识问出“这个信息我能不能用栈存着等遇到右边界再结算”说明你已经真正掌握它了。