企业官网建设流程全解析

刷题刷到第50天，遇到的第一个让人“卡住”的经典数据结构就是单调栈。相比之前学的普通栈、队列，单调栈看起来只是多了一个“单调”的约束条件，但它在解决“找下一个更大/更小元素”、“计算最大矩形面积”、“接雨水”这类问题上，能把暴力解法的 O(n²) 时间复杂度直接降到 O(n)。很多人在这一步栽跟头，不是因为不理解栈的先进后出，而是不清楚单调栈到底在维护什么信息、什么时候该弹出。

这篇博客不打算铺开讲全套算法笔记，而是从我刷题、总结错题的实际经验出发，拆解单调栈的核心原理、两类栈的选择逻辑、五道经典题型的完整推导，以及那些你在题解里看不到的边界陷阱。不管你是刚开始刷算法的初学者，还是已经刷了几百题想巩固基础的老手，这篇内容都能帮你在10分钟内把单调栈这条线彻底吃透。

1. 单调栈到底是什么：从一道面试题说起

1.1 暴力解法为什么不行

先看一道最经典的题目：给定一个整数数组，找到每个元素右边第一个比它大的元素。很多人第一反应就是双重循环，外层遍历每个元素，内层从当前位置往后找第一个更大的元素。这个思路完全正确，但时间复杂度是 O(n²)。当数组长度达到 10^5 甚至 10^6 时，跑一次就要 10^10 次操作，在绝大多数在线评测系统里都会超时。

我一开始也不太理解为什么需要引入一个新数据结构。直到我手动模拟了几组数据才发现，暴力解法最大的问题在于“重复比较”。比如数组是 [1, 3, 2, 4]，找元素 1 右边第一个更大元素时，比较了 3 之后发现答案就是 3，马上停止了。但找元素 2 时，又从头开始比较。这些比较操作之间没有任何信息可以复用，导致同一个数字被反复扫描。

单调栈的核心价值就在于“一次遍历，信息留存”。它用一个栈把已经扫描过但还没找到答案的元素保存下来，当遇到一个新的元素时，通过比较栈顶元素和新元素的大小关系，一次性把能确定答案的元素全部弹出并记录答案。每个元素最多入栈一次、出栈一次，所以总时间复杂度是 O(n)。

1.2 单调栈到底在维护什么

单调栈本质上是在维护一个“潜在候选集”。从栈底到栈顶，元素按照某种单调顺序排列——要么单调递增，要么单调递减。这个单调性不是随便规定的，它直接决定了你解决的是“右边第一个更大”还是“右边第一个更小”的问题。

拿“找右边第一个更大元素”来说，我们需要维护一个从栈底到栈顶单调递减的栈。为什么？因为当你从左到右遍历数组时，假设栈顶元素是当前已经扫描过的元素中“最有可能被下一个更大元素影响”的那个。新元素如果比栈顶大，说明栈顶元素右边的第一个更大元素就是它；此时弹出栈顶，继续看新的栈顶，直到栈顶元素比新元素大或者栈为空。这时的栈仍然是单调递减的。

很多初学者会混淆递增栈和递减栈的选择。我的记忆方式是：目标是“找更大”就用递减栈（栈内从底到顶递减），目标是“找更小”就用递增栈。这个规律虽然不能覆盖所有题型，但对90%以上的经典题目都适用。后面我会详细解释为什么，以及什么时候这个规律会被打破。

2. 单调栈的模板与两类栈的选择

2.1 单调递增栈和单调递减栈怎么分

单调栈分两种：单调递增栈和单调递减栈。这里要注意描述的是“从栈底到栈顶”的顺序。单调递增栈就是栈底最小、栈顶最大，新元素入栈时会把所有比它小的元素弹出；单调递减栈则相反，栈底最大、栈顶最小，新元素入栈时会把所有比它大的元素弹出。

选择哪种栈，核心就看你在弹出元素时想确定什么答案。用“下一个更大元素”举例：当你遇到一个比栈顶大的新元素时，这个新元素就是栈顶元素“右边第一个更大值”，所以你需要在弹出栈顶时记录答案。想要触发这种弹出，新元素必须大于正在比较的栈顶元素，从而低的先被弹出，留下的较高的留在栈底，这就是一个递减栈。

如果目标是“右边第一个更小元素”，思路完全对称：新元素比栈顶小的时候，栈顶的答案就是新元素，于是弹出栈顶，最终元素从栈底到栈顶呈递增排列。掌握这个对称性后，你就不需要死记硬背题目对应的栈类型，而是根据“何时弹出、弹出时记录什么”来现场推导。

2.2 两套模板代码

我整理了两套最精简的模板，一套用数组下标作为栈元素，另一套直接用数值。数组下标版本更通用，因为有时候我们需要的不是“更大值本身”，而是“更大的那个元素和当前元素之间的距离”，这时候必须用下标。

### 找右边第一个更大元素（单调递减栈） def nextGreaterElements(nums): n = len(nums) res = [-1] * n # 默认右边没有更大元素 stack = [] # 存下标，栈底到栈顶单调递减 for i in range(n): # 当新元素大于栈顶元素时，栈顶的答案就是新元素 while stack and nums[i] > nums[stack[-1]]: idx = stack.pop() res[idx] = nums[i] stack.append(i) return res

### 找右边第一个更小元素（单调递增栈） def nextSmallerElements(nums): n = len(nums) res = [-1] * n stack = [] # 栈底到栈顶单调递增 for i in range(n): while stack and nums[i] < nums[stack[-1]]: idx = stack.pop() res[idx] = nums[i] stack.append(i) return res

模板就两行关键代码：一个while循环负责弹出，一个append负责入栈。区别只在于比较符号是“>”还是“<”。这也是为什么我强调理解触发条件比记住模板更重要——题目一变，符号一换，如果你不理解逻辑，就只能靠死记硬背，很容易在变形题上翻车。

2.3 栈里存什么：下标 vs 数值

绝大部分情况下推荐存下标。原因有三个：第一，通过下标可以随时访问元素值，存下标等于同时保存了“值”和“位置”两种信息；第二，求解距离类问题时，比如每日温度、矩形宽度计算，你必须要用下标相减；第三，当数组存在重复元素时，存下标可以清楚地区分每个元素，避免混淆。

直接存数值的写法在简单题里看着方便，但一旦遇到需要距离、面积、区间这类计算，就不得不额外维护一个位置数组，反而多此一举。我自己刚开始刷题时就喜欢存数值，结果做“柱状图中最大矩形”这道题时怎么都算不对面积，静态调试半天才发现是宽度没算对。换成存下标后，问题迎刃而解。

3. 经典题型逐题拆解：从入门到变形

3.1 每日温度：最简单直观的入门题

LeetCode 739题的每日温度是单调栈最经典的入门题目。题目给出一组每天的温度，要求返回一个数组，每个位置表示要等多少天才能等到更高的温度，如果之后没有更高的温度就填0。比如温度是 [73, 74, 75, 71, 69, 72, 76, 73]，输出 [1, 1, 4, 2, 1, 1, 0, 0]。

这道题本质上就是“下一个更大元素”的距离版本。因为要求是“多少天后”，所以栈里必须存下标。思路是维护一个递减栈：遍历每一天的温度，如果当前温度大于栈顶下标对应的温度，说明栈顶那天的更高温度出现了，答案就是当前下标减去栈顶下标；一直弹出直到栈顶温度大于等于当前温度，然后当前下标入栈。

我第一次做这道题时犯了一个很低级的错误：在弹出循环里用了一个“if”而不是“while”。结果只处理了栈顶一个元素，后面的候选元素全部被留在栈里没有更新答案。后来我总结了一个检查方法：只要弹出操作发生在循环里，就问自己这个while需不需要继续处理多个元素——只要当前元素可能同时是多个元素的下一个更大值，就必须用while。

3.2 下一个更大元素：处理环形数组和重复值

“下一个更大元素”有几道变形题，其中最有代表性的是下一个更大元素II——数组变成了环形数组。经典做法有三种：复制数组拼成两倍长、取模遍历两轮、或者直接在遍历时对下标取模但不增加实际数组长度。最推荐取模的方式，因为内存占用少，代码也简洁。

环形数组的处理核心在于：为什么要遍历两遍？因为是环形的，某个元素的“下一个更大元素”可能绕回到它的前面。遍历一遍只能找到物理位置在右边的更大元素，绕回的部分必须再走一遍才能覆盖。但这里有个陷阱：如果第二遍重复弹出同一个元素，会导致死循环或者错误答案，所以通常配合一个计数器或者直接限制遍历次数为2n。

下一道变形题是下一个更大元素I，它给了两个数组nums1和nums2，nums1是nums2的子集，要求返回nums1中每个元素在nums2中对应位置右边的第一个更大值。这道题可以先对nums2整体跑一次单调栈，把每个元素的下一个更大值存进哈希表，然后遍历nums1直接查表。正因为栈里存的是下标，你可以同时拿到值和索引，把结果组织得非常清晰。

3.3 柱状图中最大的矩形：从“找更大”到“找更小”

柱状图中最大的矩形是单调栈题里最难理解的一道，但也是最能检验你是否真正掌握单调栈的题目。给定一组非负整数表示柱子的高度，每个柱子的宽度都是1，求这些柱子能勾勒出的最大矩形面积。

这道题的关键转折点是：枚举每个柱子作为矩形的高度时，矩形的左右边界分别是“左边第一个小于该柱子的位置”和“右边第一个小于该柱子的位置”。也就是说，你需要维护的是单调递增栈，而不是递减栈。这正是我前面说的“找更小用递增栈”的对称体现。

具体做法是：从左到右遍历，当当前柱子高度小于栈顶柱子高度时，弹出栈顶，以“栈顶柱子的高度”作为矩形高度，以“当前下标减去新的栈顶下标再减1”作为矩形宽度，计算面积并更新答案。遍历结束后，栈中可能还有剩余元素，需要再统一处理一遍，因为它们的右边界是数组末端。

我第一次做这道题时，宽度计算一直出错。后来我把整个入栈和弹出的过程在纸上画了一遍才明白：当弹出第i个柱子时，栈中它下面的那个柱子的下标，就是它左边第一个比它矮的柱子的下标；当前下标就是它右边第一个比它矮的柱子的下标。两者之间的所有柱子，高度都大于等于当前柱子，所以矩形宽度就是这个区间长度。理解到这个层面，代码就变成了一个自然的推导结果。

3.4 接雨水：单调栈技巧的集大成者

接雨水题目给出一组高度数组，每个宽度为1，问下雨后能接多少水。这道题有很多解法：双指针、动态规划、单调栈。单调栈是实现最优雅的一种，因为它可以在一次遍历中同时处理“左侧边界”、“右侧边界”和“坑的底部”这三个信息。

接雨水的思路是维护一个单调递减栈。遍历高度时，如果当前高度大于栈顶高度，说明出现了可以存水的“坑”。此时弹出栈顶元素作为坑底，新的栈顶作为左边界，当前高度作为右边界。水的高度是左右边界高度的较小值减去坑底高度，宽度是左右边界下标距离减1。

这里有一个很容易被忽略的细节：右边界必须“高于”左边界才能形成封闭坑？不一定。接雨水里弹出一次后，左边界可能还是比右边界高，也可能还是比右边界低。无论哪种情况，当前这个坑底的水量都能正确计算。所以需要不断循环弹出，直到栈顶高度大于等于当前高度，才能把这个“右边界”确定为新的围栏。这正是单调栈的精髓——它不依赖全局的比较，而是利用栈内已有的单调顺序，逐步计算每个局部坑的容量。

我记得自己第一次写完接雨水代码后，测试用例过了，但提交时有个极端用例总差一点。后来发现是因为我在循环弹出后没有把当前下标入栈，导致后续元素无法利用当前的右边界。补上这行代码后，整个逻辑就通了。做题时经常出现这种“少一行代码”导致全盘皆输的情况，所以每一步都要想清楚栈里的元素到底代表什么。

4. 实操过程与代码实现细节

4.1 边界条件的处理

单调栈代码看着短，但边界条件处理不好，照样会错。我总结出三个必须注意的边界：空栈时不能访问栈顶、数组末尾的剩余元素要统一处理、所有元素相等时不能把相等元素弹出去。

• 空栈判断：while循环里必须先判断stack不为空，再访问stack[-1]。很多初学者写代码时把顺序颠倒，导致“list index out of range”错误。我习惯写成while stack and 比较条件，利用Python的短路特性，一石二鸟。

• 末尾剩余元素：遍历完整个数组后，栈里剩下的元素说明它们右边没有满足条件的元素。在“下一个更大元素”中直接保持默认值；在“柱状图最大矩形”中需要追加一个高度为0的虚拟柱子，强制把所有元素弹出，这样就不用单独写处理逻辑了。

• 相等元素：大多数题目要求“下一个更大”而不是“下一个大于等于”，所以遇到相等元素时不要弹出栈顶。比如数组 [2, 2, 1]，右边第一个比第一个2更大的是1吗？显然不是，是1右侧没有更大的，所以第一个2的答案应该还是-1。如果你在遇到相等元素时弹出栈顶，第一个2就会被误判成2，这是非常经典的错误。

4.2 虚拟哨兵节点的妙用

在许多单调栈题目中，往数组末尾追加一个“哨兵”能大幅度简化代码。比如柱状图中最大矩形，在题解中常见写法是给原数组追加一个0，再开始遍历。为什么要加0？因为0是最小值，栈里所有比0大的柱子都会在最后一轮循环里被强制弹出，这样你就不需要在循环结束后单独写一个“处理剩余栈”的代码块。

接雨水题目也可以这样处理吗？不行。接雨水里追加0会让最后一轮把所有元素都弹出来，但弹出的过程中可能错误计算水容量，因为最后一个0高度没有任何右侧边界，根本不能构成坑。所以千万不要把柱状图那套方案直接照搬到接雨水上。要不要加哨兵，取决于这道题最后剩下的元素是否还有继续处理的价值。

我自己的习惯是：先不加哨兵，把基础版写对，再考虑用哨兵简化。因为如果一个新手第一次接触单调栈就用哨兵技巧，理解不到它背后的动机，很容易在变体题里误用。先学会完整写法，再学简化写法，知识才是立体的。

4.3 复杂度分析与空间优化

单调栈的时间复杂度是O(n)，因为每个元素最多被压入一次、弹出一次。空间复杂度是O(n)，最坏情况下所有元素严格单调递增或递减，栈里会存下全部n个元素。

在空间上有一个常见的进阶优化方向：如果题目允许修改原数组，可以把原数组本身当作栈来用。比如遇到“下一个更大元素”只要求返回结果数组，不要求保留原数组时，可以用一个指针模拟栈顶，在原数组上覆盖写入。这样能省下额外的栈空间，代码也更简洁。不过这种优化属于锦上添花，面试时可以先写标准的栈方案，再提一句可以优化，给面试官展示你的进阶思考。

还有一类问题是需要同时维护“左边第一个小于”和“右边第一个小于”两个信息。很多题解会写两次循环，一次求左边界，一次求右边界。实际上一次单调栈遍历就能同时确定这两个信息：当元素被弹出时，当前遍历位置就是右边界，栈内剩下的下一个元素就是左边界。这也是“柱状图中最大的矩形”大多数高效解法的核心。

5. 常见问题与排查技巧实录

5.1 容易出错的三个经典case

我在刷题过程中反复踩过几个坑，整理出来供大家参考：

• 输入是空数组：直接返回空结果。这种corner case最基础但最容易被忽略。很多初学者在写完主逻辑后不特意处理空数组，结果一提交就报错。建议所有单调栈题目的第一行都写上空数组保护。

• 所有元素都相同：比如 [2, 2, 2, 2]。此时“下一个更大元素”没有解，结果数组全部是-1；“每日温度”结果全部是0；“最大矩形面积”答案则是单个柱子的高度乘以1，即2。如果你在代码里用了>=作为弹出条件，这些题目的答案就会全部出错。

• 数组是严格递减：比如 [5, 4, 3, 2, 1]。找不到任何“右边更大元素”，所有答案都是-1。但如果用严格递增的弹出条件，你会把所有元素都弹出来，这不是报错，却会得到一个全错的答案。排查这类问题最好的办法就是自己手动模拟一次简短的递减序列。

5.2 排查技巧：用纸面模拟替代盲目调试

单调栈代码的调试方法和普通代码很不一样。普通代码报错后可以打印日志、打断点，但单调栈的状态变化非常快，打印日志会输出大量中间信息，反而容易看晕。我的经验是：遇到错题先别急着打印，拿一组小数据在纸上手动模拟一遍。

手动模拟时，写下三个东西：当前遍历到的下标、当前栈内元素、当前已确定的答案数组。每进入一次while循环，就在纸上划掉弹出的元素，写上更新的答案。通常模拟不到10个元素，你就能定位到是“弹出条件写反了”还是“答案更新的时机不对”。这个方法看起来原始，但对于理解单调栈这种状态依赖型算法，远比debugger高效。

我还发现，很多错误并不在栈操作本身，而在“结果数组的默认值”。比如下一个更大元素的默认值应该是-1，每日温度的默认值应该是0。如果你的默认值设错了，哪怕栈的逻辑完全正确，输出也是错的。所以我写单调栈题目时，第一步永远是确认“没有满足条件的元素时答案应该填什么”。

5.3 单调栈与单调队列的边界

刷题时经常有人把单调栈和单调队列混淆。二者有本质区别：单调栈只能在一端进行插入和弹出，解决的是“寻找某个方向的第一个最值”；单调队列是双端操作的，队尾插入、队首删除，通常用于滑动窗口问题，比如求窗口内最大值或最小值。

拿“滑动窗口最大值”那道题举例：窗口每向右移动一位，队首就要弹出不在窗口内的元素，队尾要插入新元素并弹出所有比新元素更小或相等的元素。这样队首始终是窗口最大值。这个数据结构叫单调队列，代码实现上用的是collections.deque，而不是普通list。

怎么判断一道题该用栈还是队列？核心看“信息是否还需要保留”。单调栈留下的信息是为了等待右边未知的元素来匹配；单调队列中窗口左边界移动时，过期的元素必须被移除。如果题目是寻找左右固定边界内的最值，一般用单调栈；如果是一个滑动窗口不断平移，优先考虑单调队列。这两个结构经常在综合大题的多个阶段配合出现，区分清楚了，解题思路会清晰很多。

5.4 实战中总结出的三条经验

第一，先写框架再调符号。我刷到后面发现，单调栈的代码框架就这么几行：初始化结果数组、初始化栈、遍历数组、while弹出、更新答案、入栈。我每次做题都会先把这些行写出来，再根据题目调整比较符号和答案更新逻辑。这比对着空白编辑器强行推导要快得多。

第二，正确理解“在弹出时记录答案”。单调栈最反直觉的地方是：目标答案不是在新元素入栈时记录，而是在旧元素被弹出时记录。很多初学者会习惯性在插入新元素时试图给新元素填答案，那是暴力思维在作怪。新元素的答案要等下一个更大元素出现时才能确定，所以在它自己被弹出时才能记录。

第三，不要过度崇拜单调栈。有些题目比如接雨水、最大矩形用单调栈很优雅，但如果用双指针或者动态规划更好理解，面试时选一个自己能讲清楚的方案更好。我见过很多候选人在白板上努力默写单调栈代码，结果边界条件全错，最终得分还不如用O(n²)但完全正确的暴力解。算法题的终极目标是解决问题，而不只是秀数据结构。

我个人在实际刷题中的体会是：单调栈这个技巧，本质上就是教你“延迟决策”。先让不确定答案的元素待在栈里，等信息足够时再一次性结算。这个思想不仅在算法里通用，在处理很多需要“等待后续信息”的业务场景时也很有启发。如果你刚开始学，拿每日温度练手，再挑战接雨水，逐步感受栈里元素的“生命周期”。等你哪天看到一道题，能下意识问出“这个信息我能不能用栈存着，等遇到右边界再结算”，说明你已经真正掌握它了。