单调栈详解：从暴力到O(n)的算法优化与实战应用

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：栈顶是2，2比4小，说明2不可能成为4左边任何元素的答案，因为4比它大且更靠左。弹出2。栈空，答案是 -1。把4入栈。栈现在是[4]。
• 遇到1：栈顶是4，4比1大，所以1的答案就是4。把1入栈。栈现在是[4, 1]。
• 遇到3：栈顶是1，1比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 时间复杂度实测对比

我写了一个简单的测试脚本，对比暴力解法和单调栈在不同数据规模下的耗时。

这个对比非常直观。数据量到五千的时候，暴力解法已经明显卡顿；到一万的时候，基本没法用。而单调栈在五万数据量下依然在毫秒级完成。这就是 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 常见错误速查表

实操心得：调试单调栈时，我习惯在每次循环里打印当前元素、栈的状态和结果数组。这样一眼就能看出哪一步出了问题。虽然有点笨，但比盯着代码空想快得多。

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. 从面试到实战：我的使用体会

单调栈这个结构，我最早是在刷题时学的，后来在工作中也遇到过几次实际应用。有一次做一个数据监控系统，需要找出每个指标连续上升的区间，用的就是单调栈的思路。还有一次做价格分析，需要找每个价格点之后第一个更高的价格，也是直接套的模板。

我的体会是：单调栈的价值不在于它有多难，而在于它能把一类看似复杂的问题标准化。一旦你识别出“找第一个更大/更小”这个模式，就可以直接套模板，不用每次重新推导。这种“模式识别”的能力，比记住具体代码更重要。

另外，单调栈的代码虽然短，但细节很多。弹出条件、遍历方向、相等处理、栈空判断，任何一个地方出错都会导致结果不对。我建议初学时多画图，把每一步的栈状态画出来，画个五六道题之后，基本就能形成肌肉记忆了。

最后分享一个小技巧：如果你在面试中遇到单调栈的题，可以先用手写几个小例子，展示你的推导过程，然后再写代码。这样即使代码有小瑕疵，面试官也能看到你的思路是对的。单调栈的题，思路比代码更重要。