企业官网建设流程全解析

单调栈这个专题，part01 我拆的是"下一个更大元素"那道最基础的问题，当时的思路是先把暴力解讲透，再引出单调栈怎么把 O(n²) 优化成 O(n)。不少同学看完留言说：感觉单调栈不就是"一个 while 循环加一个栈"吗，背下模板就够了。说实话，如果只是背模板，part01 确实够用了，但我在实际带人的过程中发现，一旦题目变成循环数组、变成求矩形面积、变成接雨水，光背模板的人十个里有八个会卡在"该用递增栈还是递减栈"这个坎上。

所以 part02 我特意挑了三个看起来八竿子打不着的题：循环数组的下一个更大元素、柱状图中最大的矩形、接雨水。这三道题基本覆盖了单调栈在常见笔试里九成以上的出现形式，而且它们的代码结构高度相似，核心差异只有一个：弹出栈顶时结算什么、怎么结算。把这层窗户纸捅破，你再遇到任何单调栈的变形题，就不会慌着去翻模板，而是能自己推导出单调方向。

这篇文章适合两类人：一类是刚看完基础模板，想搞明白单调栈"为什么长这样"的初学者；另一类是已经刷过这几题，但总觉得边界处理容易出错的进阶学习者。我会把每一步的"为什么"都讲清楚，也会把我在本地调试中踩过的坑一并写出来，尽量做到可以直接照着敲。

1. 重新理解单调栈：它不是数据结构，是一种淘汰策略

1.1 从 O(n²) 压到 O(n)，靠的是提前淘汰不可能成为答案的元素

我们先回到最原始的线性问题：给定一个数组，求每个元素右边第一个比它大的数，没有就返回 -1。

暴力做法没有任何技术含量：对每个下标 i，从 i+1 开始往后扫，找到第一个比 nums[i] 大的就停下。最坏情况是数组单调递减，每个元素都要扫到数组末尾，总复杂度是 O(n²)。当 n 是十万级别时，这个复杂度在严格评测环境下基本会超时。

单调栈的做法很多人已经知道了：从左到右遍历，维护一个栈，遇到新元素时，只要它比栈顶元素大，就弹出栈顶并记录"栈顶的答案就是当前元素"，最后把当前元素入栈。

这里最容易被忽略的关键点是：为什么被弹出的元素可以永远不再参与后续比较？因为它已经找到了右边第一个比它大的值，后续就算出现更大的值，也不再是"第一个"了，留着没有任何意义。反过来，那些没有被弹出的元素，说明到目前为止还没遇到比自己大的值，它们继续留在栈里等待未来的更高值。整个算法就是靠着"一旦被确认答案就立刻淘汰出场"这个策略，让每个元素最多只进栈一次、出栈一次，整体复杂度严格 O(n)。

很多初学者第一次看到 while 内嵌在 for 循环里，会怀疑这明明看起来像两层循环，怎么可能线性？原因在于 while 里每弹出一个元素，这个元素就永久离开栈，所有弹出操作的总次数不超过 n，而不是每次 for 迭代都触发 n 次弹出。这和双指针"两个指针看起来在循环里动，总共只移动 2n 次"是同一个道理，属于复杂度分析里典型的"均摊思想"。

1.2 方向感怎么找：先问自己找的是"更大"还是"更小"

我给基础薄弱的同学讲单调栈时，会让他们先记一句方向口诀：找右边第一个更大，用从栈底到栈顶递减的栈；找右边第一个更小，用从栈底到栈顶递增的栈。这里我把递增递减统一按"从栈底到栈顶"的方向来定义，因为不同资料里的说法经常相反，自己先约定好能省掉很多混乱。

为什么找"更大"反而用递减栈？我们站在栈顶的角度理解：这个栈里存的是"还没找到答案的候选者"，越靠近栈顶的候选者离当前元素越近。新元素 x 到来时，如果 x 比栈顶大，说明栈顶等到了答案，弹出结算；如果 x 比栈顶小，说明栈顶还要继续等，此时 x 作为一个值更小、位置更靠右的新候选者，就应该压在栈顶，等待将来某个更大的元素先把 x 结算掉，再轮到栈里的老元素。这样整个栈从底到顶保持递减，非常自然。

但我要在这里打个预防针：这个口诀只适用于"求最近更大/更小元素"的问题。后面最大矩形用的是递增栈，接雨水用的是递减栈，如果硬套"找更大就用递减栈"，会直接翻车。我建议大家把口诀当作入门拐杖，最终还是要学会从问题语义里重新推导方向。这也是 part02 的核心目标之一。

2. 先解决循环数组：下一个更大元素 II

2.1 环形数组到底改变了什么

原版"下一个更大元素"是线性数组，每个元素只看右边。循环数组的意思是：最后一个元素的下一个要回到下标 0 继续找，整个数组首尾相接，绕一圈如果还没找到，答案才是 -1。这个题型的现实场景很常见，比如一周内找下一个温度更高的日子、循环排班的销售数据里找下一个更高的价格点。

最直觉的解法是把原数组复制一份拼在后面，得到一个长度为 2n 的数组，然后对这个"加长数组"跑一遍普通的线性单调栈算法，最后只取前 n 个位置的结果。这个思路完全正确，代码也好写，缺点是需要额外 O(n) 的空间来拼数组。实际上我们完全可以不复制数组，而是用取模运算模拟环形：让下标 i 从 0 遍历到 2n-1，每次用 i % n 拿到真实下标，数组本身从头到尾只穿一次。两种写法本质上一样，取模版更省空间，也更考验细节。

2.2 单调栈 + 取模遍历的完整实现

这里有一个大部分教程没有点透的细节：第二轮遍历时，到底要不要继续把元素压入栈？

先看一个不加限制的朴素版本：

def nextGreaterElements(nums): n = len(nums) ans = [-1] * n st = [] for i in range(2 * n): idx = i % n while st and nums[st[-1]] < nums[idx]: top = st.pop() ans[top] = nums[idx] st.append(idx) return ans

这个版本能通过大部分测试样例，因为即使第二轮重复入栈，重复的索引再次被弹出时赋的值和第一次一样，结果不会错。但问题在于，栈里会出现同一个下标的多个副本，比如数组 [1, 2, 1]，第一轮结束时栈里保留着下标 0 和 2 对应的两个数值 1；第二轮遇到第二个 1 时，又把它push进去，栈里两个 1 的索引各出现一次，后面遇到 2 时这些副本会被逐个弹出，白白浪费空间，逻辑上也不干净。

更严谨的做法是：第一轮遍历负责把索引入栈，第二轮只负责让还没结算的元素继续等待被更大的元素弹出，不再新增候选：

def nextGreaterElements(nums): n = len(nums) ans = [-1] * n st = [] # 从栈底到栈顶递减，存索引 for i in range(2 * n): idx = i % n while st and nums[st[-1]] < nums[idx]: top = st.pop() ans[top] = nums[idx] if i < n: st.append(idx) return ans

为什么这样不会漏？因为第一轮结束时，栈里剩下的元素都是"在当前线性范围内没有找到更大值"的候选者，它们的答案还没确定。第二轮从头再扫一遍，等价于把这些剩余候选者暴露给环形的后半段数组。只要某个候选者的"下一个更大值"真的存在，它一定会在这个加长的环形扫描里被某个下标命中；如果真的不存在，ans 中保留的初始值 -1 就是正确答案。

2.3 两个容易写错的边界细节

第一个细节是严格大于和大于等于的区别。题目说"下一个更大"，指的是严格大于。所以弹栈条件必须写成nums[st[-1]] < nums[idx]，相等时不弹出。如果你把<改成<=，遇到数组 [1, 1] 时，第二个 1 会把第一个 1 弹出，误认为它的答案是"它自己"，这在逻辑上是荒谬的。什么时候才考虑<=？只有题目明确要求"下一个不小于"，或者题目本身要求统计相等元素的某种贡献时，才需要调整比较符。

第二个细节是栈里到底存值还是存索引。我在所有单调栈代码里都统一存索引，原因是：一旦题目要求计算下标距离（每日温度）或者区间宽度（最大矩形），存值就完全帮不上忙，你还得额外维护一个平行下标数组。存索引，需要数值时用nums[st[-1]]去取，这是最不容易出错的标准姿势。

3. 柱状图中最大的矩形：单调栈第一次"跨界"

3.1 为什么说这道题是分水岭

"下一个更大元素"系列的单调栈，思维链路只有一个：找到答案就弹出。柱状图中最大的矩形不一样，它要求在一串高度不等的柱子中，找到面积最大的连续矩形。很多同学做到这道题才发现，单调栈原来还能用来划分区间、维护左边界和右边界，这是思维上的一次重要升级。

先看暴力做法：枚举每一根柱子，把它当作矩形的高度，然后向左右两侧扩展，直到遇到比它矮的柱子为止，宽度就是左右矮柱之间的跨度，面积 = 高度 × 宽度，取最大值。这个做法的问题很明显：如果数组是单调递增的，每根柱子都要向外扩展到整个数组的最远端，总复杂度 O(n²)，高度数组一大就必挂。

优化的突破口在于：对任意一根柱子来说，以它作为高度形成的最大矩形，其左右边界一定恰好是"左右两侧第一个比它矮的柱子"。比如高度数组 [2, 1, 5, 6, 2, 3] 中，以高度 5 的柱子为中心，左边第一个比 5 矮的是高度 1，右边第一个比 5 矮的是高度 2，所以 5 能形成的最大矩形宽度就是这两根矮柱子之间的跨度。换句话说，只要我们能高效求出每根柱子"左右两侧最近的更小元素"，就能在线性时间内算出每个候选矩形的面积。而"左右两侧最近的更小元素"恰恰是单调栈最擅长处理的问题。

3.2 递增栈如何同时给出左右边界

我们维护一个从栈底到栈顶递增的栈，存的是柱子下标。遍历到第 i 根柱子时，如果它的高度比栈顶高度小，那么对栈顶那根柱子来说：右边第一个比它矮的柱子就是当前的 i。它的左边第一个比它矮的是谁？答案是把栈顶弹出后，新的栈顶。为什么可以这么肯定？因为栈里的元素从底到顶严格递增，如果弹出前栈顶是某段较高区域的右端，那么它下面的那个元素，一定是在它左边并且高度严格小于它的最近柱子。如果中间还存在更矮的柱子，那根更矮的柱子早就应该在之前把栈顶元素挤出去了，不可能还留在栈里。

所以"弹出时结算"就成了最大矩形的核心动作：弹出栈顶柱子，记录它的高度 h，新的栈顶就是左边界 left，当前下标 i 就是右边界 right，矩形面积 = h × (right - left - 1)。注意宽度用的是两个边界之间的柱子数，所以要减一。

我拿一个具体例子完整走一遍。heights = [2, 1, 5, 6, 2, 3]，为了统一处理边界，先在前后的位置各补一个高度 0 的哨兵，变成 [0, 2, 1, 5, 6, 2, 3, 0]，下标从 0 到 7。

遍历到下标 1 的高度 2，栈空，直接入栈。下标 2 的高度 1 来了，它比栈顶 2 矮，弹出 2。此时栈顶是下标 0 的哨兵 0，所以左边界是 0，右边界是 2，宽度 = 2 - 0 - 1 = 1，面积 = 2 × 1 = 2，这就是高度 2 的柱子能形成的最大矩形。把高度 1 入栈。下标 3 的高度 5 比栈顶 1 高，入栈；下标 4 的高度 6 比栈顶 5 高，入栈。下标 5 的高度 2 来了，比栈顶 6 矮，弹出 6，左边界是下标 3 的 5，右边界是下标 5 的 2，宽度 = 1，面积 = 6。继续弹出 5，左边界是下标 2 的 1，右边界是下标 5 的 2，宽度 = 5 - 2 - 1 = 2，面积 = 10。此时栈顶高度 1 小于当前高度 2，停止弹出，把下标 5 的 2 入栈。后面继续遍历到哨兵 0 时还会弹出一系列元素，但最大面积已经锁定在 10。

3.3 哨兵节点：让边界情况回归主流程

最大矩形题的经典翻车点有两个。第一个是遍历结束后栈里可能还剩着若干柱子没有结算，它们都是递增留在栈里、始终没遇到更矮右边界的柱子。如果不在数组末尾补一个高度 0 的哨兵，就必须写一段额外的 while 处理残局，还要手动把 right 设成 n，非常容易漏算或者把宽度算错。第二个翻车点是左边界为空：如果弹出的是栈里唯一一根真实柱子，弹出后栈为空，再取 st[-1] 就会越界报错。

给原数组前后各加一个高度 0 的哨兵，能一次性解决这两个问题。前面的哨兵保证真实柱子弹出时栈里始终还有一个更矮的底，永远不会空；后面的哨兵高度为 0，比任何真实柱子都矮，遍历到它时会把栈里所有剩余柱子全部强制弹出并结算。这个技巧看起来像 hack，实际上是把所有特殊边界都统一成了主流程里的普通一次弹出，强烈建议每一道最大矩形题都固定加上。

def largestRectangleArea(heights): heights = [0] + heights + [0] n = len(heights) st = [] ans = 0 for i in range(n): while st and heights[st[-1]] > heights[i]: h = heights[st.pop()] left = st[-1] right = i ans = max(ans, h * (right - left - 1)) st.append(i) return ans

代码里弹栈条件我用的>而不是>=。对于相等高度的连续柱子，用>会把它们都留在栈里，直到最后一个相等高度被弹出时，左边界会一口气跨越到更早的位置，从而算出完整宽度。用>=也能得到正确结果，但我个人偏爱>，因为它更准确地表达了"严格更矮才构成边界"的语义，调试时心智负担更小。

4. 接雨水：用单调栈把凹槽一层层填满

4.1 接雨水的本质是找凹槽

接雨水这道题也是经典中的经典。最容易想到的解法是双指针：从左往右扫一遍记录每个位置左侧的最大高度，从右往左扫一遍记录右侧的最大高度，每个位置能接到的水量等于min(左侧最大, 右侧最大) - 当前高度。时空复杂度都是 O(n)，非常好理解。

但双指针版的缺点是它把每个位置当作独立单元去算，没有真正体现"区间"关系。如果题目改成环形数组接雨水、要求输出每段积水的位置、或者要统计每个位置上方具体接了多少水，双指针写起来就很难受。这时候单调栈就体现出优势了：它天然维护"左边界、底部、右边界"这组三元关系，能把每一段积水当成一个可独立结算的区间。

积水的本质是凹槽。一段水要想存在，必须有一个低洼的"底"，左右两侧都有一根比底高的柱子作为边界。我们从左到右遍历柱子，维护一个从栈底到栈顶递减的栈。当新柱子高度大于栈顶时，意味着栈顶这个"底"等到了右边界，可以结算它正上方的那一层水了。

4.2 为什么弹出一次只结算"一层"水

和最大矩形"弹出一次就彻底结算一根柱子"不同，接雨水每次弹出只补一层水，高度取左右两边较矮的那个边界减去底部高度。这一点是很多初学者理解卡壳的地方，我用一个最简单的例子拆开讲：[2, 0, 1]。

下标 0 的高度 2 入栈。下标 1 的高度 0 比栈顶 2 小，说明 0 是个凹槽底，入栈。下标 2 的高度 1 来了，它比栈顶 0 大，弹出 0，栈顶是下标 0 的 2，所以左边界高度 2，右边界高度 1，底部高度 0，这一层水的高度 = min(2, 1) - 0 = 1，宽度 = 2 - 0 - 1 = 1，补水量 = 1。把下标 2 的高度 1 入栈，总水量是 1，完全正确。

如果凹槽是嵌套的，比如 [3, 0, 2, 1, 2]，过程会更有意思。下标 4 的高度 2 到来时，先弹出下标 3 的底部 1，形成一层浅水；接着比较新的栈顶，也就是下标 2 的高度 2，它和当前高度相等，不满足严格大于，不弹出，当前下标 4 入栈。等以后遇到更高的柱子时，才会把下标 2 的高度 2 当作"底"再补更高的一层。所以单调栈法是自下而上逐层补水，结构上等价于把每个凹槽按深度拆成若干水平层，每层都在它对应的右边界出现时结算，不会漏算也不会重复叠加。

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] h = min(height[left], height[i]) - height[bottom] w = i - left - 1 if h > 0: ans += h * w st.append(i) return ans

这段代码有两个极容易写错的点。第一，弹出 bottom 后必须立刻判断栈是否为空，如果为空，说明左边没有任何比底更高的柱子，这个凹槽没有左边界，装不了水，直接 break。漏掉这个判断就会在下一行 st[-1] 处越界。第二，每次补水的宽度不是固定 1，而是右边界到左边界之间的柱子数，也就是 i - left - 1，因为左右边界之间可能夹着多个已经被弹出的低洼柱子，它们共同属于这一层水的水平区间。

4.3 双指针和单调栈怎么取舍

接雨水这道题，我的原则是：求职笔试只求稳的时候，双指针更省心；但如果想借一道题充分理解单调栈的区间维护能力，或者题目带上了"环形""输出区间"之类的变体，单调栈是更好的突破口。两道解法的时间复杂度都是 O(n)，空间上双指针甚至可以做到 O(1)，所以单纯比性能没有太大意义。真正的差异在于：双指针把问题拆成了"每个位置的水量"，单调栈把问题拆成了"每个凹槽的水量"，后者明显更贴近物理过程，扩展性也更强。

学习阶段我建议把两种解法都写一遍。写完之后你会意识到，它们本质上都在做同一件事——取两侧较低边界的高度差，只是单调栈把左右边界的配对关系显式地暴露给了程序员，这对接后续变种题有巨大帮助。

5. 单调栈问题排查与模板沉淀

5.1 一张表判断该用哪种单调方向

动手写代码前，先用十秒钟确定"该用递增栈还是递减栈"，能避开大部分方向性错误。下面这张表里的"递增/递减"统一指从栈底到栈顶，"弹出条件"里的比较也按题目要求是否严格来调整。

最大矩形本质上是在找左右两侧最近更小的边界，所以用递增栈，对应表格第三行；接雨水是在找左右两侧最近更大的边界，用递减栈，对应表格第四行。如果遇到一道完全陌生的题，先抽象一下：它需要的是更小的边界还是更大的边界？结算的是单点答案还是一段区间？这两个问题能快速帮你锁定方向。

5.2 存索引还是存值：这是一道送分题，但总有人丢分

我在带人刷题的过程中发现，栈里存值是高频翻车点。一旦题目涉及宽度、距离、跨度，你存的数值完全派不上用场，还得额外用一个平行数组去记下标，或者在栈里塞一个二元组，代码瞬间变丑。正确做法是统一存索引，需要数值时用数组下标去取。哪怕这道题只关心数值大小，也建议统一存索引，因为这样代码迁移到"每日温度""最大矩形"这类需要下标的题时，几乎不用改动结构。

5.3 翻车现场：常见 Wrong Answer 原因对照

我整理了带训练营这段时间大家犯错最多的几个点，按出现频率排了个序。对照这份清单去检查自己的代码，通常比逐行读代码效率高不少：

• 栈存了值而不是下标，导致后面算宽度时无从下手，被迫重构代码。
• 弹出栈顶后没有判断栈是否为空，直接取 st[-1]，在接雨水里必炸。
• 循环数组的第二轮又无脑入栈，导致栈内出现重复索引，结果碰巧正确但逻辑混乱。
• 最大矩形没加哨兵，遍历结束后剩余栈元素没有结算，或者单独处理时 right 取值越界。
• 比较符搞反：需要严格大于时用了 >=，让相等元素互相结算，输出一堆"自己等于自己"的可笑答案。
• 答案数组没有初始化成 -1，等到真的找不到更大值时输出什么都不对。

我在本地调试单调栈题时会固定准备两组极端样例：单调递增数组 [1, 2, 3, 4, 5] 和单调递减数组 [5, 4, 3, 2, 1]。前者保证每个元素都能快速找到答案，后者保证所有元素都没答案，用来检验框架会不会在极端情况下崩掉。只要这两组数据通过，再跑题目自带的示例，基本就能确定代码没有结构性错误。

5.4 单次遍历、双次遍历和"复制数组"的取舍

最后一个值得聊的问题是遍历次数。循环数组天然需要两轮遍历，因为首尾相接；普通线性数组只有一轮。但在实际笔试中还会出现一类变体：题目要求把数组复制一份后对长度为 2n 的序列做单调栈，最后截取前 n 个结果。这时候取模版本和复制版本都能用。取模版本省空间，可读性稍差；复制版本更直观，但空间翻倍。我个人的习惯是笔试严格控制内存时选取模，日常练习时选复制数组，因为本地调试时拼接后的数组更容易打印观察，逻辑不容易写错。两种方式本质没有优劣，重要的是你脑子里清楚：第二轮的作用是"让剩余候选者看到环形数组后面的部分"，而不是"重新开始一轮新计算"。

我在实际辅导中最后都会跟学习者强调，单调栈不是刷题模板里的背诵章节，它的核心是"利用单调性提前淘汰无效候选，让每个元素只有一次入栈、一次出栈的机会"。part01 到 part02 的跨度，就是从"会套模板"到"能根据问题语义选择单调方向"的过程。刷完循环数组、最大矩形、接雨水这三道题，你会发现它们表面毫无关联，底层其实是同一套"维护候选区间"的机制在运作。

最后分享一个我自己的小习惯：每写完一道单调栈题，我会手动把"极端单调递增"和"极端单调递减"两组样例跑一遍，再在草稿纸上写出每次弹出时的 left、right 和结算值。这个动作看起来原始，但比任何调试工具都更能暴露你对边界条件的理解漏洞，尤其是哨兵位置和宽度公式这类细节。坚持几次之后，你对"弹出时结算"这个动作的敏感度会明显提升。