上周帮一个准备跳槽的朋友做模拟面试他卡在 LeetCode 739 “每日温度”上暴力解法写得行云流水可面试官一追问“能不能优化到 O(n)”他就卡住了。这个问题我在陪人刷题、带新人准备算法面试时遇到过太多次——大家其实都听说过单调栈也知道它是刷题利器但真到动手时却不清楚什么时候该用、栈里到底存值还是存索引、单调性该往哪个方向维护。这篇就专门把“单调栈”掰开揉碎地讲一遍包括它解决什么算法问题、两个通用模板怎么推导、经典题型长什么样以及我自己实际刷题和带人过程中踩过的坑。如果你正在准备算法工程师面试、刷 LeetCode 或者打竞赛这篇文章能帮你把同类题一次性打通。1. 单调栈到底在解决什么问题1.1 先看一道让暴力解法当场超时的题“每日温度”原题是这样给你一个整数数组 temperatures每天的温度记录在里面你要返回一个数组 answeranswer[i] 表示从第 i 天开始需要等多少天才能等到一个更高的温度。如果之后都没有更高的温度返回 0。最直观的暴力解法就是双层循环def dailyTemperatures(temperatures): n len(temperatures) ans [0] * n for i in range(n): for j in range(i 1, n): if temperatures[j] temperatures[i]: ans[i] j - i break return ans这个思路没错代码也对可一旦 n 来到 10^5 级别最坏情况下要执行大约 n^2/2 次比较也就是 50 亿次操作。题目限时 1 秒的话基本可以直接送出 TLETime Limit Exceeded。面试里出现这类题常见节奏就是你先把暴力解写出来面试官点点头然后追问“能不能优化到 O(n)”。如果对单调栈没提前做过系统梳理很多人到这里就慌了。暴力解法的问题在哪右边更高的那个元素可能被后面很多次重复扫描每一次都在重新比较完全没有复用之前已经得到过的信息。单调栈优化掉的就是这部分重复劳动。1.2 四个方向的“第一个更大/更小”问题从更抽象的层面看单调栈统一解决的是一类问题给定一个数组对每个元素找出它左边/右边第一个比它大/比它小的元素。这四个方向排列组合基本覆盖了单调栈的原始应用场景。方向要找的元素典型应用右边第一个更大Next Greater Element每日温度、LeetCode 496右边第一个更小Next Smaller Element接雨水变体、股票价格跨度左边第一个更小Previous Smaller Element柱状图最大矩形左边第一个更大Previous Greater Element某些区间统计题一旦拿到了这些原始信息就可以进一步加工出距离、区间宽度、面积、水量等答案。这也是为什么单调栈能通吃“每日温度”“最大矩形”“接雨水”这些看起来差别很大的题——它们的底层都离不开“最近边界”这个概念。1.3 为什么单调栈能优化到 O(n)单调栈的核心理念是维护一个从栈底到栈顶保持单调递增或递减的栈然后在元素进栈、出栈的过程中利用“出栈的时机”来确定答案。为什么每个元素只处理常数次因为每个下标最多只会被 push 进栈一次也最多只会被 pop 出来一次。一次遍历中虽然 while 循环可能连着弹出很多元素但整体来看总出栈次数等于入栈次数不超过 n。用均摊分析总时间复杂度是 O(n)而不是表面看到的 O(n^2)。我习惯用一个生活类比去理解这件事想象一群人按顺序排队进场队伍保持“身高从左到右递增”的秩序。这时来了一个特别高的人排在队尾那么队伍里所有比他矮的人都可以立刻转身看到“右边第一个比自己高的正是这个人”看完就可以离场去填写答案了。每个人离场时都只被“身后第一个更高的那个人”触发一次之后再也不需要回头比较其他人。暴力做法是每个人进场后还要反复向后看而单调栈让每个人都只被最近的第一次触发带走这就是优化点所在。2. 单调栈模板与原理拆解2.1 到底该用单调递增栈还是递减栈这一节是初学者最常搞混的地方。我的判定方法是先想清楚“你希望谁触发弹栈”再用“触发弹栈的那个方向”去判断。如果你要找的是“右侧第一个更大的元素”那么栈底到栈顶应该保持单调递减也就是栈顶最小。当新元素比栈顶更大时它就会持续触发弹栈把那些“都在等一个更大元素”的栈顶逐个弹出而当前元素正是它们的答案。如果你要找的是“右侧第一个更小的元素”则维护单调递增栈栈底到栈顶递增遇到更小的新元素时触发弹栈。简单记忆口诀找更大的用递减栈因为需要“大”来触发弹栈找更小的用递增栈因为需要“小”来触发弹栈。单调性描述的都是从栈底到栈顶的方向。这个规则确实容易记反我在带新人时最有效的纠正办法就是拿一个非常短的数组比如 [2, 1, 3]手动模拟一遍看看在哪个方向下输出了正确结果。不要死背一推就明白。2.2 通用模板代码与逐行解释先给最通用的模板求每个位置的“右侧第一个更大元素”。def next_greater_elements(nums): n len(nums) res [-1] * n # 找不到答案时默认 -1 st [] # 栈里存的是索引不是值 for i in range(n): while st and nums[i] nums[st[-1]]: # 当前元素 nums[i] 是栈顶元素右侧第一个更大元素 res[st.pop()] nums[i] st.append(i) return res对应的 C 版本vectorint nextGreaterElements(vectorint nums) { int n nums.size(); vectorint res(n, -1); vectorint st; for (int i 0; i n; i) { while (!st.empty() nums[i] nums[st.back()]) { res[st.back()] nums[i]; st.pop_back(); } st.push_back(i); } return res; }逐行理解一下。第一栈里存的是索引不是值。原因是有了索引可以随时取到值但反过来存了值没法知道位置更没法算“距离”。第二while 循环里的比较符号是关键条件。这里维护的是单调递减栈所以凡是“比栈顶大”的新元素都能把栈顶结算掉。第三全部遍历完后栈里剩下的元素说明它们右边没有更大的元素保持默认 -1 即可。把比较符号换成就是右侧第一个更小元素模板把遍历方向改成从右往左也可以求左侧第一个更大元素。但我更建议优先掌握“从左往右扫描 弹栈结算”这一种写法绝大多数题目都能靠它延伸出来。2.3 复杂度分析与手推演示用一个小例子手推一遍比任何口诀都直观。数组 [2, 1, 5, 6, 2, 3]求每个位置的右侧下一个更大元素。i0nums[0]2栈空push(0)栈[0]i1nums[1]1不比栈顶 2 大push(1)栈[0, 1]i2nums[2]5比栈顶 1 大pop(1)res[1]5仍比新栈顶 2 大pop(0)res[0]5然后 push(2)栈[2]i3nums[3]6比栈顶 5 大pop(2)res[2]6push(3)栈[3]i4nums[4]2比栈顶 6 小push(4)栈[3, 4]i5nums[5]3比栈顶 2 大pop(4)res[4]3比新栈顶 6 小push(5)栈[3, 5]最终 res [5, 5, 6, -1, 3, -1]。可以看到 6 右边没有更大元素3 右边没有更大元素所以保持 -1。整个过程中每个索引最多入栈一次、出栈一次。虽然是嵌套循环实际总操作次数 O(n)。空间复杂度 O(n)因为最坏情况下栈里要存接近全部下标。3. 经典题型实战从模板到变形3.1 入门LeetCode 496 下一个更大元素 I这道题的题干是nums1 是 nums2 的子集需要返回一个数组每个元素是 nums1 中对应数字在 nums2 中的下一个更大元素。题目比较绕但拆解起来很简单先用单调栈把 nums2 全量处理一遍得到“每个值 - 它右侧第一个更大值”的映射关系再遍历 nums1 查表。def nextGreaterElement(nums1, nums2): map_next {} st [] for x in nums2: while st and x st[-1]: map_next[st.pop()] x st.append(x) return [map_next.get(x, -1) for x in nums1]注意这版代码栈里存的是值而不是索引因为本题只要求输出元素值不涉及距离。虽然我之前建议“优先存索引”但也要学会灵活变通。这道题相当于单调栈的入门口味一遍扫描建映射再查询。时间 O(nm)n 是 nums2 长度m 是 nums1 长度。类比一下我们要给每个人找到他身后第一个更高的人先把所有的人都排一次队谁高谁矮提前定好再拿名单来查。nums1 中即使只有少数元素也不需要重新扫描 nums2。3.2 进阶LeetCode 739 每日温度的最优解这道题真正发挥“存索引”价值的是结果要求返回“天数差”而不是“温度差”。假如栈里只存温度值等到弹栈那一刻你根本不知道这个温度和当前下标之间隔了多少天。所以这里必须存索引。def dailyTemperatures(temperatures): n len(temperatures) ans [0] * n st [] for i in range(n): while st and temperatures[i] temperatures[st[-1]]: prev st.pop() ans[prev] i - prev st.append(i) return ans代码逻辑和模板几乎一样唯一的区别是结算时写的是ans[prev] i - prev也就是“当前位置 - 栈顶位置”的天数差。这个写法很固定很多变形题只要把结果从“值”换成“距离”即可核心思想不变。我在带新人时发现不少人会把ans[prev]写成temperatures[i]把“天数”写成“温度”因为没分清题目要的是值还是距离。建议写代码前先问自己一句话题目要返回的是元素值还是一段长度、宽度或面积判断清楚再动手。3.3 硬核进阶LeetCode 84 柱状图中最大的矩形这是单调栈最经典也最容易劝退的一题。题面是给定 n 个非负整数表示柱状图每根柱子的高度求能勾勒出的最大矩形面积。暴力想法是枚举每一根柱子作为“最小高度”然后分别向左右延伸找到第一个比它矮的柱子用“右边界 - 左边界 - 1”作为宽度。但这样每个柱子都要左右扫描又是 O(n^2)。单调栈的优化思路是用单调递增栈维护柱子高度当遇到一根比栈顶矮的新柱子时栈顶柱子就到了“必须结算”的时机。因为对栈顶而言它右边第一个更矮的正是当前柱子而左边第一个更矮的是它在栈中弹出后的新栈顶。于是宽度可以确定。def largestRectangleArea(heights): heights [0] heights [0] # 前后加哨兵 0 n len(heights) st [] max_area 0 for i in range(n): while st and heights[i] heights[st[-1]]: h heights[st.pop()] left st[-1] 1 # 左边界是弹出后新栈顶的右边一位 right i - 1 # 右边界是当前柱子的左边一位 max_area max(max_area, h * (right - left 1)) st.append(i) return max_area这里加两个 0 是很实用的哨兵技巧。开头加 0避免栈空时还要特判 left结尾加 0会把栈里还没结算的柱子全部强制弹出。我自己最初写这题时就是因为忘了处理结尾残留的柱子导致面积算少加上哨兵后代码干净很多。手动模拟 [2, 1, 5, 6, 2, 3]预处理后为 [0, 2, 1, 5, 6, 2, 3, 0]遇到 1 时2 出栈h2left1right1宽度 1面积 2。遇到下标 5 的 2 时6 出栈h6left4right4宽度 1面积 6接着 5 出栈h5left3right4宽度 2面积 10。最后 0 触发剩余元素结算3 出栈面积 32 出栈面积 81 出栈面积 6。最大面积是 10。也就是高度 5 的柱子向左右扩展到边界形成的 5 * 2 10。这个题非常适合训练对“结算时机”的判断把它彻底搞懂整个单调栈体系就通了大半。3.4 综合LeetCode 42 接雨水的单调栈写法接雨水通常第一反应是双指针或动态规划但单调栈同样能解而且思路很自然用单调递减栈存柱子的下标当当前柱子比栈顶高时栈顶弹出的柱子就是一个“凹槽底部”水量由两侧较矮的边界高度减去底部高度决定宽度是两侧边界下标之差减一。def trap(height): n len(height) st [] ans 0 for i in range(n): while st and height[i] height[st[-1]]: bottom st.pop() if not st: break # 左侧没有边界无法积水 left st[-1] width i - left - 1 h min(height[left], height[i]) - height[bottom] if h 0: ans width * h st.append(i) return ans这题的核心判断是只有当前柱子比栈顶高时栈顶元素才可能是凹槽底。因此栈里保留的是一个递减序列也就是从高到低排列的“潜在边界”。对比双指针解法单调栈版本不需要事先计算左右最大值逻辑更统一也更容易延伸到其他“找边界”的题目。3.5 一张表看懂单调栈变形题地图题目变体点核心技巧难度参考LeetCode 496下一个更大元素 I单调栈处理母数组哈希表查值简单LeetCode 739每日温度栈存索引结果算距离中等LeetCode 84柱状图中最大矩形递增栈 前后哨兵 0困难LeetCode 42接雨水递减栈 双边界计算困难LeetCode 503下一个更大元素 II循环数组遍历两轮中等LeetCode 402移除 K 位数字单调栈 贪心结果最小中等LeetCode 962最大宽度坡先递减栈再反向扫描中等这七道题足够覆盖单调栈的大部分套路。你会发现底层的“入栈、弹栈、结算”三件事完全一致变的只是栈内单调方向、栈里存的是值还是索引以及结果如何加工。把这套“形态”看熟以后遇到新题第一反应就不会是去硬凑写法而是先问这道题要找的边界是哪个方向4. 常见错误与调试技巧实录4.1 栈里存值还是存索引取决于结果形态这是我被问到最多的问题。统一结论是只要代码里需要用到下标差、左右边界、区间宽度就一定存索引如果只是求“元素值”并且不需要位置信息比如 496存值会让代码更短。但为了风格统一我仍然推荐一开始就习惯存索引。存索引的好处是你可以随时通过数组取到值而存值却补不回位置信息。养成“默认存索引”的习惯能少踩很多坑。4.2 单调方向写反后的自查方法方向写反是新手最常见的错误表现是结果全错或者部分错。我推荐的自查流程先确定“弹栈时机”——比如求右侧第一个更大元素弹栈条件必须是nums[i] nums[st[-1]]然后确定栈内单调性——因为弹的是栈顶“小的”所以栈底到栈顶是递减的。如果题目答案是求“右侧第一个更小”就把比较符号改成栈自然变成递增。不要记那些容易混淆的“递增栈对应什么题”的表而是记一套推导逻辑能触发弹栈的元素就是你正在找的那个方向的元素。每次写代码前花十秒做一个这样的推导正确率会高很多。4.3 边界条件与残留在栈里的元素很多人在写单调栈时忽略了一个关键点遍历结束后栈里可能还剩一堆“右边没有更大/更小元素”的下标。模板里 res 初始化为 -1 或 0可以自然兜底但像 84 题那种需要每一个栈顶都完成结算的题目就一定要额外加哨兵 0 或写收尾循环。我的经验是写题之前先把“数组末尾之后的虚拟元素”想好再决定是否需要哨兵。这个思考比调试省时间得多。另外栈空的时候也要特别小心比如接雨水里弹出一个 bottom 之后如果栈空了说明左边没有边界积水无法封闭必须直接 break否则会算出负数宽度或者错误水量。4.4 三分钟定位问题的调试方法如果输出不对我最常用的办法是在弹栈那一行加上打印例如 Python 里写print(i, st, pop, prev)然后把一个长度为 3 或 4 的小数组跑一遍对照自己的手推结果。单调栈的调试难点不在代码编译错误而在逻辑和预期不一致。把每次弹栈时结算的是谁、被哪个元素触发打印出来几乎立刻就能看出是方向反了、下标算错了还是边界条件没覆盖。面试现场如果遇到类似问题也可以坦诚地对面试官说“我打印一下栈的运行情况再确认”这比低着头干想更有效。调试不是丢人的事能快速定位问题本身就是一种能力。5. 刷题顺序与面试实战心得5.1 什么时候应该想到单调栈我给自己总结的触发词是某个元素需要找到“左边或右边最近的、比它大/小的元素”。只要题目里出现“下一个更大”“下一个更小”“左侧第一个更矮”“最近边界”这类描述大概率都能往单调栈靠。还有一类间接场景最大矩形、接雨水、最长有效括号的某几种解法都是把问题转化成了“找左右边界”之后再用单调栈解决。相反如果题目要求的是“全局最大/最小”或者“滑动窗口最值”优先考虑堆或者单调队列不要硬套单调栈。数据结构选型的关键是看信息复用方式单调栈适合“每个位置只需要知道最近一次破坏单调性的人”单调队列适合“窗口内持续维护最值”堆适合“不关心顺序只关心最值”。5.2 面试时怎么把单调栈思路讲清楚面试考官不希望你上来就背模板。我建议按这个顺序讲先描述暴力解法并说出 O(n^2) 的代价然后提出“能不能让每个元素只结算一次”接着说明用栈维护一个单调序列遇到能触发弹栈的元素时就完成对栈顶的结算最后分析每个元素进出栈各一次所以总复杂度 O(n)。这样讲面试官能立刻 get 到你的思路是从复杂度痛点出发的而不是背题。需要手写代码时注意先写注释理清三件事栈存什么、什么时候弹、弹的时候结算什么。我做模拟面试时光是这一个习惯就能让候选人的代码通过率提升一大截。5.3 我个人的刷题顺序建议如果从零开始我推荐按这个顺序刷496入门→ 739距离→ 84面积和哨兵→ 42积水→ 503循环数组→ 402贪心结合→ 962综合。前四题是核心后三题是拓宽视野。这个顺序的考虑是先掌握最简单的右侧更大元素模板再逐步引入索引、距离、边界、环形数组每个新变量每道题只引入一个新的难点不会让人一次性面对太多抽象概念。实际效果比我当初乱序刷要扎实得多。每次刷完一题我还会顺手在笔记里画一遍栈的变化图把“谁在什么时候弹出来、被谁弹出来”写清楚下次复习时一眼就能捡起来。我在陪人刷题和日常带团队时最深的体会是单调栈不是靠背模板就能真正掌握的它需要在纸上手推几个例子理解每一次出栈背后的“结算”含义。面试前一天与其刷十道新题不如把 739、84、42 这三道经典题从头推导一遍效果反而好得多。希望这篇能把单调栈的底层逻辑讲透下次再看到“右边第一个更大”“最大矩形”“接雨水”这类题你能比上一秒的自己更快反应过来。