搞算法刷题的朋友对“代码随想录”这套训练营应该不陌生day46排在栈与队列之后、进入单调栈专题的第一天。说实话我当年刷到这一章的时候对“单调栈”三个字是有点发怵的名字听起来像某种高级数据结构代码又短得离谱几行就写完但自己动手时就是绕不过弯来。后来把专题刷完才明白这东西与其说是一个数据结构不如说是一种“利用历史信息做状态压缩”的思考方式。这篇东西不是给零基础讲单调栈定义的我默认你已经知道栈是先进后出、知道暴力解法为什么会超时。我想聊的是代码随想录这个题单里单调栈专题1的核心思路怎么串起来什么时候该想到用单调栈、栈里到底存什么、递增和递减怎么选、边界为什么老是写错以及我当初踩过的那些坑。如果你正在跟训练营的进度或者刚刷到LeetCode热题里的每日温度、接雨水、柱状图最大矩形这篇文章应该能帮你把那几行代码真正吃透。1. 先搞明白单调栈解决的是哪一类问题1.1 三句话判断能不能用单调栈我总结了一个特别粗鲁的判断法问三个问题是不是要找某个元素“左边或右边第一个比它大/小的元素”是不是要求这个“更近的更大/更小”和当前元素之间的距离暴力解法是不是明显要O(n²)而数据规模在10⁵以上三个问题里命中两个基本就可以考虑单调栈了。经典的每日温度问题就是给你一组温度数组让你求“对于每一天要等几天才能等到更高的温度”。暴力解法是每一天往后扫描最坏情况是数组单调递减每一天都要扫到末尾O(n²)直接跪。而单调栈解法只需要一遍遍历、每个元素入栈一次出栈一次整体O(n)空间也是O(n)。这个场景太典型了不是要全局的最大值最小值而是要“局部范围内、第一个满足大小关系的那个位置”。你如果在问题描述里看到“第一个”“下一个”“最近的”这类限定词脑子里就要给单调栈亮个灯。1.2 为什么暴力解法会TLE而单调栈不会暴力之所以慢核心在于大量的比较动作被重复计算了。举例来说数组[73, 74, 75, 71, 69, 72, 76, 73]找每天的下一个更高温度。暴力法下第0天要依次比较74、75、找到76才停第2天又得从71开始扫到76。每一种“后面有更大的元素”的组合都被反复扫描。单调栈的思路本质上是把比较逻辑反过来不是站在每个元素的角度往后找目标而是每来一个新元素主动去“收割”栈顶那些已经确定答案的元素。新元素入栈时只要它比栈顶大那栈顶元素的下一个更大元素就是它此时弹出栈顶、记录答案。这样一来每一对“前小后大”的元素关系只被计算一次整体比较次数是O(n)级别的。一句话总结单调栈是用空间记录“还没找到答案的历史元素”让每个元素只等一次不等一万次。2. 关键认知栈里存的是索引不是值2.1 为什么索引比值重要我第一次写单调栈自然而然地往栈里存了元素值结果写到最后要算距离的时候就傻眼了——你只知道栈顶的值是74却不知道它在原数组的第几个位置下标拿不到距离怎么算代码随想录的题解里反复强调栈里存数组下标。原因有三通过下标随时可以拿到对应值arr[stack[-1]]就能取到值和索引信息都不丢。算距离时直接减下标就行比如当前索引i减去栈顶索引stack[-1]一步到位。出现重复值时索引是唯一的不会像值一样产生混淆。所以不管题目是叫你返回“下一个更大元素本身”还是返回“距离”一律存索引。这个习惯一定要一开始就立住。2.2 从“按钮排队”理解单调栈的工作过程我把单调栈想成一个排队窗口栈底的元素是最早来的“老人”栈顶是最新的“新人”。这个队伍维持一个单调性——要么从底到顶单调递减要么单调递增取决于你找的是更大还是更小的元素。拿每日温度来说我们维护的是一个栈底到栈顶单调递减的栈也就是说栈顶是整个栈里最小的那个元素对应的索引。每次来一个新温度就做一件事只要新温度比栈顶温度高说明栈顶那个老兄已经等到他后面的第一个更高温了而且这个“后面”就是现在因为新元素就是紧挨着它出现的。这个“从栈顶往下收割”的过程就是单调栈最核心的动作。你会发现栈里存的全是“命运未定”的元素一旦答案确定立刻弹出绝不留恋。3. 单调栈专题核心题拆解四道题吃透一个套路代码随想录单调栈专题1里核心的题不少但如果要挑四道最能打通任督二脉的我个人的顺序是每日温度、下一个更大元素I、接雨水、柱状图中最大的矩形。前两道是“寻找下一个更大元素”的直球题后两道是“用左右第一个边界求面积”的变形。3.1 每日温度最纯粹的模板题目给定数组temperatures返回一个数组answeranswer[i]表示第i天之后多少天才有更高的温度没有则为0。我的Python模板代码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 ans核心理解这条while循环新元素是“审查官”它一来先看栈顶是不是比自己小。如果栈顶比它小那栈顶的答案就是当前索引弹出。弹出后继续看新的栈顶因为新元素可能比栈里一连串元素都大比如温度[70, 71, 72]到72这一天70和71的答案都要更新所以必须写成while而不是if。栈里留下的元素永远是还没找到答案的而且从栈底到栈顶保持递减。为什么因为一旦出现“新元素比栈顶大”的情况栈顶就被弹走了只有新元素不大于栈顶时它才有资格入栈并压在栈顶所以新元素一定是栈里最小的。复杂度上每个元素入栈一次、出栈最多一次整体O(n)。空间上最坏情况是数组单调递减所有元素都留在栈里O(n)。注意这个模板里判断条件是“严格大于”才弹出。也就是temperatures[i] temperatures[stack[-1]]不是。如果改成遇到重复温度时会出问题——相等温度不该被视为“更高的温度”提前弹出会导致答案错误。这是我见过最典型的边界错误之一。3.2 下一个更大元素I单调栈哈希表打配合题目nums1是nums2的子集返回nums1中每个元素在nums2中对应位置的下一个更大元素。这题有趣的地方在于它不是在原数组上直接求答案而是先要把nums2的“下一个更大元素映射”算出来存进哈希表再查表输出。def nextGreaterElement(nums1, nums2): stack [] nxt {} # 记录每个元素的下一个更大元素 for x in nums2: while stack and x stack[-1]: nxt[stack.pop()] x stack.append(x) # 栈里剩下的元素没有下一个更大元素可以不处理默认查不到就是-1 return [nxt.get(x, -1) for x in nums1]注意这题栈里存的是值而不是索引因为题目只要求返回元素本身不要求算距离。这就呼应了前面的观点栈里存什么取决于你最终要什么。这道题传达了一个很重要的思路单调栈的结果不一定要当场填进答案数组它可以先构建一个“映射表”或者“辅助数组”给后面的问题用。这种解耦方式在更复杂的题里非常常见。3.3 接雨水从“竖着算”到“横着算”接雨水大概是单调栈专题里最容易让人卡住的一道题。暴力解法和按列求解都相对好理解但单调栈解法里那个“宽度是左右下标的差”让很多人一头雾水。代码长这样def trap(height): ans 0 stack [] for i in range(len(height)): while stack and height[i] height[stack[-1]]: top stack.pop() if not stack: break left stack[-1] width i - left - 1 h min(height[left], height[i]) - height[top] ans width * h stack.append(i) return ans这里的关键在于单调栈解法不是“按每一列竖着算雨水”而是“按每个凹槽横着分层算”。我给你捋一下栈底到栈顶是递减的。当新元素比栈顶高时说明栈顶这个位置形成了一个“谷底”。这个谷底能装多少水要看它的左边界新栈顶也就是left和右边界当前i分别有多高。那为什么宽度要减1而不是直接用i减去弹出来的那个索引因为我们算的是一个“平台区域”比如凹槽里水面高度达到了左右边界中较矮的那个这个水层覆盖了top到left、top到i之间的整个区间宽度是left和i的距离再减去top自己占的那一格。这个解法每次弹出top时算的是“以top为底、以left和i为左右墙的一个薄层水”。同一个位置可能在多次弹出中被算到不同高度的水层这些水层加起来就是总水量。暴力求法是站着算单调栈是躺着分片算。理解了这个区别就理解了为什么单调栈解法里的宽度和高度长得和直觉不太一样。3.4 柱状图中最大的矩形单调递增栈和哨兵技巧这题是接雨水的“镜像问题”接雨水是找凹槽最大矩形是找凸起。它不再是求“下一个更大的元素”而是求“每个柱子作为矩形高度时左右两侧第一个比它矮的位置”。左右边界一确定宽度就确定了面积就能算出来。def largestRectangleArea(heights): # 关键技巧末尾补一个高度为0的柱子保证栈最后能弹空 heights.append(0) stack [] ans 0 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这题栈是单调递增的从栈底到栈顶高度递增。每当新柱子比栈顶矮就说明栈顶那根柱子的右边界出现了同时由于栈是递增的它左边的柱子一定比它矮或者没有左边的柱子所以左边界就是弹出它之后新的栈顶。末尾补0是个非常实用的小技巧。如果不补这个0遍历结束后栈里还会剩下一堆递增的柱子没处理你还得写一段额外的收尾循环来统一计算。补一个0之后遍历到最后一个位置时0比栈里所有柱子都矮会把栈全部弹空所有面积都在主循环里算完了。这个哨兵思路在别的地方也经常用值得记下来。4. 常见问题与排查技巧实录4.1 经典翻车现场while写成if单调栈的while循环写错成if是最常见的错误。写成if的结果是新元素只能“收割”一个比它小的栈顶但如果它比栈里一连串元素都大后面的那些元素就永远错过正确答案了。我之前刷每日温度时自测用例全过一提交就WA。后来打印日志才发现问题出在遇到连续上升温度时会漏掉中间元素的答案。排查方法很简单在第3个测试用例里故意构造一个[1, 2, 3, 4]这种严格递增序列。正确答案是[1, 1, 1, 0]用if写的答案却是[0, 0, 0, 0]——一眼就能看清问题。4.2 栈里放值还是放索引按需选择但要形成条件反射这个问题我在前面专门说过但它是高频翻车点值得再提一次。凡是答案需要“距离”“宽度”“区间长度”的必须存索引凡是答案只要元素值本身的可以存值。我的建议是除非你非常有把握不然一律存索引。索引能随时取值但值不能随时算距离。宁可代码多写一行arr[stack[-1]]也别在需要算距离的时候两眼一抹黑。4.3 递增还是递减一句话口诀很多人到考场上一紧张就分不清该用递增栈还是递减栈。我的判断方法很粗暴要找“下一个更大的元素”时维护的是递减栈栈顶最小。要找“下一个更小的元素”时维护的是递增栈栈顶最大。为什么因为“找更大”时新元素比栈顶大就弹出栈顶并记录答案栈里的元素从底到顶就是递减的反过来“找更小”时新元素比栈顶小就弹出栈里从底到顶就是递增的。用接雨水和最大矩形区分接雨水找的是“比它高的左右墙”所以是递减栈最大矩形找的是“比它矮的左右边界”所以是递增栈。4.4 边界条件三连问写单调栈最容易在边界上翻车我总结了三个自测必问数组为空时代码会不会crash循环不进来栈是空的答案数组长度也对基本没问题。数组单调递增时栈会不会一直空比如每日温度[1, 2, 3, 4]每个元素都能弹出前一个栈永远只有当前元素答案是[1, 1, 1, 0]。数组单调递减时答案是不是全0比如[4, 3, 2, 1]没有任何元素能弹出别人答案全0。但要确认栈里积压了大量元素没有出栈这个过程会不会导致TLE不会因为虽然栈塞满了但只是入栈操作循环体依然是O(n)。我写了一个通用的小调试模板每次怀疑逻辑不对就加上两行打印for i in range(n): while stack and condition: idx stack.pop() # 记录答案 stack.append(i) # print(stack, ans) # 调试用观察栈的变化和答案的填充过程打上几轮日志基本就能清楚地看到栈里哪些元素在等等到什么时刻被谁“解锁”比自己瞎猜快得多。4.5 常见问题速查表症状可能原因解决办法答案全为0栈里存了值算距离时算不出索引差改成存索引用索引取值答案偏小while误写成if漏掉了连续弹出检查循环条件是否用了while相等元素答案错误比较条件用了提前弹出了相等值根据题意控制是否严格大于接雨水结果偏大/偏小没判断弹栈后栈是否为空就计算宽度弹出后先判断if not stack: break最大矩形漏算末尾没加哨兵0栈里的剩余矩形没被处理原数组末尾追加0或写收尾循环死循环弹栈时索引操作错误导致索引没推进打印索引和栈内容定位5. 单调栈的进阶认知与扩展方向5.1 循环数组中“下一个更大元素”的取模技巧有些题会让数组首尾相连比如循环数组。这时候最常用的技巧是“逻辑上把数组复制一遍”遍历范围从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]]: top stack.pop() ans[top] nums[idx] if i n: stack.append(i) return ans这个技巧的核心是“虚拟延长”而不是真的拼接数组既省空间又避免修改原数据。注意入栈条件里用if i n避免同一个元素被重复入栈两次。5.2 单调栈在二维场景中的应用单调栈并不局限于一位数组。比如力扣85题“最大矩形”本质上是把二维矩阵按行拆成一维高度数组然后每一行调用一次“柱状图中最大矩形”的单调栈解法。这种“维度压缩”的思想在很多矩阵题里都适用——先把问题压成一维再套用一维算法。我在这一步的理解是单调栈本身是一种“工具”不是一种“题型”。它解决的核心问题是“最近边界”而“边界”这个概念在二维场景里同样存在。学会把二维问题拆成多个一维问题是刷题水平提升的一个重要分水岭。5.3 单调栈和动态规划的关系很多人在刷题时会问单调栈能做的题动态规划能不能做答案是很多都能但复杂度不一样。以接雨水为例动态规划需要先从左到右、从右到左各扫一遍记录前缀最大值和后缀最大值空间复杂度O(n)时间也是O(n)。单调栈解法也是O(n)时间但空间上更灵活——不需要额外数组只用栈。我的体会是动态规划更“直白”好理解单调栈更“聪明”代码更短但对理解深度的要求更高。面试时如果能先用暴力说清思路再过渡到单调栈优化会显得对问题理解得很透彻。6. 刷单调栈专题的实战经验与个人建议6.1 先手动画栈再写代码我再多强调一点单调栈的代码很短但理解门槛其实不低。如果你一上来就盯着代码看很容易误以为自己懂了实际上手一写就露馅。我的做法是在纸上画一个数组手动维护一个栈。数组[73, 74, 75, 71, 69, 72, 76, 73]为例第0天73栈空入栈栈为[0]第1天7474 73弹出0答案ans[0] 1入栈1栈为[1]第2天7575 74弹出1答案ans[1] 1入栈2栈为[2]第3天7171 75入栈3栈为[2, 3]第4天6969 71入栈4栈为[2, 3, 4]第5天7272 69弹出4ans[4] 1继续看72 71弹出3ans[3] 272 75停止入栈5栈为[2, 5]第6天7676 72弹出5ans[5] 176 75弹出2ans[2] 4入栈6栈为[6]第7天7373 76入栈7栈为[6, 7]栈里最后剩下两个元素没有更高的温度答案保持0。手推过一遍代码就是在复现这个过程每一步都有据可依写起来自然就不虚了。6.2 形成“四步走”的肌肉记忆我建议你在刷完这个专题后把下面这套流程固化到脑子里判断问题是不是要找“下一个/上一个更大/更小”。确定栈的单调性找更大用递减栈找更小用递增栈。确定栈存什么要距离就存索引只要值也可以存值。写while循环弹出边弹出边记录答案最后把当前元素入栈。再加上一个补丁特殊场景需要哨兵比如最大矩形补0或循环数组取模2n就在标准流程之外单独记忆。6.3 从代码随想录的训练节奏中获得的体会代码随想录把单调栈放在栈与队列之后、二叉树之前这个顺序是有道理的。它要求你熟练掌握栈这个数据结构的特性又不需要太复杂的递归思维。我就是在这个节点上完成了从“用栈实现功能”到“用栈优化算法”的思维转变。day46作为这个专题的起点四道经典题正好覆盖了单调栈最核心的几种形态。如果时间有限我的建议是优先把每日温度和柱状图最大矩形吃透然后其他题都会顺很多。最后再分享一个小技巧刷完单调栈专题后把“接雨水”和“最大矩形”这两道题放在一起对照着看。它们一个找凹槽、一个找凸起一个用递减栈、一个用递增栈一个是找更大的左右墙、一个是找更小的左右界。弄懂这一对镜像题你会发现单调栈的理解深度会上一整个台阶。这个对照思考的习惯我觉得比多刷十道同类型的题更有价值。