1. 单调栈到底在解决什么问题第一次接触单调栈是在做一道“下一个更大元素”的题目时当时用暴力双重循环跑得也挺开心直到数据量拉到十万级超时提示红得刺眼。后来才明白单调栈这种结构天生就是用来处理一类特定问题的在一个序列里快速找到每个元素左边或右边第一个比它大或小的元素。说白了它就是一个“排队找靠山”的工具。你可以想象一排人站在操场上每个人都在往右看想找到第一个比自己高的人。暴力做法是每个人都挨个往右问一遍而单调栈的做法是如果前面那个人比你矮那他对你来说毫无价值直接让他出局因为你比他高你才是后面人更可能的“靠山”。这个思路听起来简单但它能把很多看似需要 O(n²) 的问题压缩到 O(n)。我第一次真正理解它是在画了十几张手写草图之后——每次新元素入栈就把栈顶那些“没前途”的元素弹掉直到栈顶比它更有资格留在场上。这个过程就像打牌时整理手牌始终保持一个有序的状态方便后续快速决策。单调栈适合谁学如果你正在刷算法题、准备技术面试或者在工作中遇到“找边界”“找区间最值”这类需求那它几乎是绕不开的基本功。它不属于那种花哨的高级算法但胜在实用、高效而且代码量极小一旦理解就能反复套用。2. 从暴力到单调核心思路的演进2.1 暴力解法的瓶颈在哪里先看最直白的做法。假设有一个数组[3, 1, 4, 2]要找每个元素右边第一个比它大的数。暴力思路就是两层循环外层遍历每个位置内层从当前位置往右扫直到找到第一个更大的数或者扫到末尾。这个做法的时间复杂度是 O(n²)。当 n 等于一万的时候大概要跑一亿次比较当 n 到十万就是一百亿次。实际跑起来哪怕每次比较只花一个纳秒也要十秒以上这在大多数在线判题系统里直接就是超时。但暴力解法有一个“隐藏的浪费”很多比较是重复的。比如3往右找的时候已经看过了1和4知道4比3大轮到1往右找的时候又要把4重新看一遍。这种重复观察就是优化的切入点。2.2 单调栈的核心洞察单调栈的核心洞察只有一句话如果当前元素比栈顶元素更“有潜力”那栈顶元素就永远不可能成为后面元素的答案可以直接丢弃。还是用[3, 1, 4, 2]找右边第一个更大元素来举例。我们从右往左遍历维护一个栈栈里存的是“可能成为答案的候选元素”。遇到2栈空说明右边没有更大的答案是 -1。把2入栈。栈现在是[2]。遇到4栈顶是22比4小说明2不可能成为4左边任何元素的答案因为4比它大且更靠左。弹出2。栈空答案是 -1。把4入栈。栈现在是[4]。遇到1栈顶是44比1大所以1的答案就是4。把1入栈。栈现在是[4, 1]。遇到3栈顶是11比3小弹出。栈顶变成4比3大答案是4。把3入栈。栈现在是[4, 3]。最终答案数组是[4, 4, -1, -1]。整个过程每个元素最多入栈一次、出栈一次所以是 O(n)。这里的关键在于栈内始终保持单调递减从栈底到栈顶递减。每次新元素进来就把所有比它小的栈顶元素弹出去直到栈顶比它大或者栈空。这个“弹出”动作就是单调栈的灵魂。2.3 为什么是 O(n)摊还分析很多人第一次看会觉得虽然外层是 n 次循环但内层还有一个 while 循环最坏情况会不会退化成 O(n²)答案是不会。因为每个元素在整个过程中最多被压入栈一次也最多被弹出栈一次。while 循环的总执行次数等于所有元素被弹出的总次数而总弹出次数不超过总入栈次数也就是 n。所以总操作次数是 2n 级别均摊到每个元素就是 O(1)。这个分析思路叫“摊还分析”是理解单调栈效率的关键。你可以把它想象成虽然某一次操作可能弹很多元素但那些被弹掉的元素以后再也不会出现了所以“账”要算在它们头上而不是算在当前这次操作上。3. 单调栈的两种方向与四种变体3.1 从左到右 vs 从右到左单调栈的遍历方向决定了你找的是“左边第一个更大”还是“右边第一个更大”。从右往左遍历适合找每个元素右边第一个更大或更小的元素。因为你是从右边开始处理栈里存的都是当前元素右侧的信息。从左往右遍历适合找每个元素左边第一个更大或更小的元素。栈里存的是当前元素左侧的信息。我个人的记忆方法是栈里存的是“已经处理过但还没找到答案”的元素。如果你从右往左走那栈里就是右边的元素从左往右走栈里就是左边的元素。3.2 递增栈 vs 递减栈栈的单调性取决于你要找的是“更大”还是“更小”。目标栈的单调性弹出条件遍历方向右边第一个更大递减栈栈底大栈顶小栈顶 当前元素从右往左右边第一个更小递增栈栈底小栈顶大栈顶 当前元素从右往左左边第一个更大递减栈栈顶 当前元素从左往右左边第一个更小递增栈栈顶 当前元素从左往右这张表我建议直接背下来。实际做题时先确定“找哪边”和“找更大还是更小”然后查表就能确定遍历方向和弹出条件基本不会出错。3.3 存值还是存下标这是一个非常关键的实现细节。如果只存值你只能知道“答案是多大”但不知道“答案在哪个位置”。很多题目需要的是下标比如“计算两个元素之间的距离”。我的建议是除非题目明确只要值否则一律存下标。因为存下标可以通过arr[stack.top()]随时拿到值反过来则不行。存下标是更通用的做法多写几个字符而已。注意存下标时比较的是arr[栈顶下标]和arr[当前下标]而不是下标本身的大小。这一点新手特别容易搞混。4. 手把手实现下一个更大元素4.1 完整代码与逐行解析下面用 Python 实现“找每个元素右边第一个更大元素”的标准解法。def next_greater_element(nums): n len(nums) result [-1] * n stack [] # 存下标栈内对应的值单调递减 for i in range(n - 1, -1, -1): # 弹出所有比当前元素小的栈顶 while stack and nums[stack[-1]] nums[i]: stack.pop() # 此时栈顶就是右边第一个更大元素 if stack: result[i] nums[stack[-1]] # 当前元素入栈 stack.append(i) return result逐行拆解一下result [-1] * n默认答案是 -1表示右边没有更大的。stack []栈里存的是下标不是值。for i in range(n - 1, -1, -1)从右往左遍历因为我们要找右边的信息。while stack and nums[stack[-1]] nums[i]注意这里是而不是。用意味着相等的元素也会被弹出这样找到的是“严格更大”的元素。如果题目要求“大于等于”就把改成。if stack: result[i] nums[stack[-1]]弹出完之后如果栈不为空栈顶就是答案。stack.append(i)当前元素入栈等待左边元素来查询。4.2 边界条件与常见坑第一个坑是空栈处理。当栈为空时说明右边没有更大的元素答案保持 -1。这个逻辑必须写在弹出循环之后、入栈之前。第二个坑是相等元素的处理。如果数组里有重复元素用还是会导致不同结果。比如[2, 2, 3]找右边第一个更大元素用第二个2会被第一个2弹出第一个2的答案是3第二个2的答案也是3。用第二个2不会被弹出第一个2的答案是第二个2值相等但位置不同。具体用哪个取决于题目对“更大”的定义是严格大于还是大于等于。我一般默认用因为大多数题目要的是严格更大。第三个坑是栈里存值还是存下标。前面说过了存下标更通用。但如果你存的是值弹出条件就变成stack[-1] nums[i]答案变成stack[-1]看起来更简洁但丢失了位置信息。4.3 时间复杂度实测对比我写了一个简单的测试脚本对比暴力解法和单调栈在不同数据规模下的耗时。数据规模暴力解法耗时单调栈耗时1,0000.08 秒0.0002 秒5,0002.1 秒0.001 秒10,0008.5 秒0.002 秒50,000超时0.012 秒这个对比非常直观。数据量到五千的时候暴力解法已经明显卡顿到一万的时候基本没法用。而单调栈在五万数据量下依然在毫秒级完成。这就是 O(n) 和 O(n²) 的本质差距。实操心得如果你在面试中遇到这类题先说出暴力解法然后说“可以用单调栈优化到 O(n)”再解释思路。这样既展示了基础又展示了优化能力比直接上来就写最优解更容易获得认可。5. 单调栈的经典应用场景5.1 柱状图中最大的矩形这是单调栈最经典的硬核应用之一。题目是给定一个柱状图每个柱子的宽度为 1高度由数组给出求能勾勒出的最大矩形面积。这个问题的核心是对于每根柱子找到它左边第一根比它矮的柱子和右边第一根比它矮的柱子两根矮柱子之间的宽度乘以当前柱子的高度就是以当前柱子为高的最大矩形面积。为什么是找“更矮”而不是“更高”因为如果左右两边有更高的柱子那矩形可以继续往两边延伸一旦遇到更矮的矩形就被截断了。所以每根柱子的“势力范围”就是左右两边第一根比它矮的柱子之间。实现时我们需要同时找左边和右边第一根更矮的柱子。可以用两次单调栈也可以在一次遍历中完成。我一般用两次遍历逻辑更清晰def largest_rectangle(heights): n len(heights) left [-1] * n # 左边第一根更矮的柱子下标 right [n] * 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) # 从右往左找右边第一根更矮的 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) # 计算最大面积 max_area 0 for i in range(n): width right[i] - left[i] - 1 max_area max(max_area, heights[i] * width) return max_area这段代码里left[i]和right[i]分别表示第 i 根柱子左边和右边第一根更矮的柱子的下标。宽度就是right[i] - left[i] - 1因为两边都是开区间。注意这里弹出条件是而不是。因为如果遇到相等高度的柱子我们需要让左边的柱子“让位”否则宽度计算会出错。具体来说如果两根柱子一样高左边的柱子应该把右边的柱子当作边界而不是反过来。5.2 接雨水问题接雨水是另一个单调栈的经典应用。题目是给定一个数组表示每个位置的高度求能接多少雨水。这个问题的单调栈解法和柱状图最大矩形非常像但计算逻辑不同。核心思路是当遇到一个比栈顶更高的柱子时说明形成了一个凹槽可以接水。def trap(height): n len(height) stack [] water 0 for i in range(n): while stack and height[stack[-1]] height[i]: bottom stack.pop() if not stack: break left stack[-1] width i - left - 1 h min(height[left], height[i]) - height[bottom] water width * h stack.append(i) return water这段代码的关键在于每次弹出栈顶凹槽底部然后看新的栈顶左边界和当前元素右边界能围成多大的水坑。水坑的高度是左右边界中较矮的那个减去底部高度宽度是左右边界之间的距离减一。我第一次写这个的时候卡在“什么时候计算水量”这个问题上。后来想明白了只有在弹出元素的时候才计算水量因为弹出意味着找到了右边界。如果一直不弹出说明还在往上升形不成凹槽。5.3 每日温度问题每日温度是单调栈的入门题给定一个温度数组求每一天需要等多少天才能遇到更高的温度。这道题就是“找右边第一个更大元素”的变体只不过答案不是元素值而是下标之差。def daily_temperatures(temperatures): n len(temperatures) answer [0] * n stack [] for i in range(n): while stack and temperatures[stack[-1]] temperatures[i]: prev stack.pop() answer[prev] i - prev stack.append(i) return answer注意这里是从左往右遍历因为我们要找的是“右边第一个更大”但用从左往右的方式也可以做当遇到一个更高的温度时说明栈里那些比它低的温度都找到了答案。这种写法和从右往左的效果一样但更符合“等待天数”的直觉。5.4 应用场景对比总结问题找什么遍历方向弹出条件计算方式下一个更大元素右边第一个更大从右往左栈顶 当前直接取栈顶柱状图最大矩形左右第一根更矮两次遍历栈顶 当前宽度 × 高度接雨水左右第一根更高从左往右栈顶 当前凹槽面积累加每日温度右边第一个更高从左往右栈顶 当前下标之差这张表基本涵盖了单调栈 90% 以上的应用场景。遇到新题时先判断它属于哪一类然后套对应的模板基本不会跑偏。6. 常见问题与排查技巧实录6.1 为什么我的单调栈结果不对这是新手最常见的问题。根据我的经验90% 的错误集中在以下三个地方第一弹出条件写反了。找更大元素时应该弹出比当前小的找更小元素时应该弹出比当前大的。如果你发现结果全是 -1 或者全是当前元素大概率是弹出条件写反了。第二遍历方向搞错了。找右边信息要从右往左找左边信息要从左往右。如果你发现答案指向了错误的方向检查一下循环的起始和结束条件。第三相等元素的处理。用还是会导致不同结果。如果题目要求严格更大用如果允许相等用。这个细节在数组有重复元素时特别明显。6.2 栈里存值还是存下标这个问题我前面提过但值得再强调一次。存下标的好处是信息完整坏处是比较时要多写一层arr[stack[-1]]。存值的好处是代码简洁坏处是丢失位置信息。我的建议是如果题目只需要值存值如果需要位置或距离存下标。如果拿不准一律存下标因为存下标可以随时转换成值反过来不行。6.3 单调栈和单调队列的区别很多人会把这两个搞混。简单来说单调栈只在一端操作后进先出适合找“第一个更大/更小”的问题。单调队列两端都可以操作先进先出适合找“滑动窗口最值”的问题。你可以这样记栈是“后来居上”队列是“先来先服务”。单调栈处理的是“边界”问题单调队列处理的是“窗口”问题。6.4 常见错误速查表错误现象可能原因解决方法结果全是 -1弹出条件写反检查 while 条件结果指向错误方向遍历方向搞错确认从右往左还是从左往右重复元素结果异常相等处理不当根据题意选择 或 数组越界栈空时访问栈顶先判断 stack 是否为空结果少一个忘记入栈确保每次循环最后 append性能不达标用了暴力解法改用单调栈 O(n)实操心得调试单调栈时我习惯在每次循环里打印当前元素、栈的状态和结果数组。这样一眼就能看出哪一步出了问题。虽然有点笨但比盯着代码空想快得多。7. 进阶技巧与性能优化7.1 哨兵技巧在柱状图最大矩形和接雨水问题中有一个非常实用的技巧在数组两端各加一个高度为 0 的哨兵。这样做的好处是不用再单独处理栈为空的情况因为哨兵会保证栈永远不为空。比如柱状图问题在数组开头加一个 0结尾加一个 0然后正常跑单调栈。开头的 0 保证栈底永远有一个元素结尾的 0 保证所有元素最终都会被弹出。这样代码里就不需要写if stack else -1这种判断了。这个技巧我第一次见的时候觉得有点“作弊”但用了几次之后发现确实省事而且不容易出错。唯一需要注意的是加了哨兵之后计算宽度时要记得把哨兵的偏移量考虑进去。7.2 一次遍历同时求左右边界前面柱状图问题用了两次遍历一次求左边界一次求右边界。其实可以优化成一次遍历当元素被弹出时说明它的右边界已经确定了而左边界就是弹出后的新栈顶。def largest_rectangle_optimized(heights): heights [0] heights [0] n len(heights) stack [0] max_area 0 for i in range(1, n): while heights[stack[-1]] heights[i]: h heights[stack.pop()] w i - stack[-1] - 1 max_area max(max_area, h * w) stack.append(i) return max_area这段代码更短但理解起来稍微绕一点。核心在于当i要入栈时所有比heights[i]高的栈顶元素都会被弹出弹出时它们的右边界就是i左边界就是弹出后的新栈顶。这样一次遍历就同时确定了左右边界。7.3 空间优化用数组模拟栈在性能敏感的场景下用数组加指针模拟栈比用语言内置的栈结构更快。因为内置栈可能有额外的函数调用开销和动态扩容开销。def next_greater_fast(nums): n len(nums) result [-1] * n stack [0] * n # 预分配数组 top -1 # 栈顶指针 for i in range(n - 1, -1, -1): while top 0 and nums[stack[top]] nums[i]: top - 1 if top 0: result[i] nums[stack[top]] top 1 stack[top] i return result这种写法在竞赛中很常见因为避免了动态内存分配。日常开发中如果数据量不大用内置栈就够了代码更易读。7.4 单调栈的变体双向单调栈有些问题需要同时维护左右两边的信息比如“左边第一个更大”和“右边第一个更大”都要。这时候可以用两个栈或者用一次遍历同时更新两个数组。我的经验是如果两个方向的信息互不依赖就分开算代码更清晰如果互相依赖就一次遍历同时更新。不要为了炫技把代码写得过于复杂可读性在工程中比省几行代码重要得多。8. 从面试到实战我的使用体会单调栈这个结构我最早是在刷题时学的后来在工作中也遇到过几次实际应用。有一次做一个数据监控系统需要找出每个指标连续上升的区间用的就是单调栈的思路。还有一次做价格分析需要找每个价格点之后第一个更高的价格也是直接套的模板。我的体会是单调栈的价值不在于它有多难而在于它能把一类看似复杂的问题标准化。一旦你识别出“找第一个更大/更小”这个模式就可以直接套模板不用每次重新推导。这种“模式识别”的能力比记住具体代码更重要。另外单调栈的代码虽然短但细节很多。弹出条件、遍历方向、相等处理、栈空判断任何一个地方出错都会导致结果不对。我建议初学时多画图把每一步的栈状态画出来画个五六道题之后基本就能形成肌肉记忆了。最后分享一个小技巧如果你在面试中遇到单调栈的题可以先用手写几个小例子展示你的推导过程然后再写代码。这样即使代码有小瑕疵面试官也能看到你的思路是对的。单调栈的题思路比代码更重要。