企业官网建设流程全解析

第一次认真学单调栈，是因为我在刷一道非常经典的题时被卡住了：给定一个数组，要求求出每个元素右边第一个比它大的数。我当时第一反应是暴力两重循环，代码倒是三分钟写完了，一提交直接超时。后来在讨论区看到有人提到“单调栈”三个字，说实话当时觉得这名字挺吓人的，感觉像是什么高深的数据结构。真正花了一个周末把它啃下来之后才发现，单调栈的思想一点都不复杂，本质上就是一个“有原则地维护栈内有序性”的普通栈，只是这个“原则”用对了地方，能把很多O(n²)的问题直接压到O(n)。

这篇内容就是我想把当时踩过的坑、总结出来的套路，以及C++实现时的细节一次性讲清楚。无论你是刚接触算法的初学者，还是准备面试想快速复习这部分内容的开发者，只要能看懂数组和栈的基本操作，这篇文章应该能让你少走不少弯路。我会从暴力解法的痛点开始讲，一步步拆解单调栈的原理、C++代码模板、四类经典题型，以及我在实际刷题过程中遇到的那些“没写在题解里”的坑。

1. 为什么需要单调栈：先从暴力解法的痛点说起

单调栈这东西，很多人一上来就背模板，结果换个题目就不会用了。我觉得问题恰恰出在“只知道模板长什么样，不知道模板要解决什么问题”。所以我先把问题源头讲透。

1.1 一个再常见不过的题目场景

先看这个最经典的场景：给定一个整数数组，对数组中的每一个元素，找出它右边第一个比它大的元素，如果不存在就返回-1。比如数组是[2, 1, 4, 3]，那么答案是[4, 4, -1, -1]。

这个题在LeetCode上的名字叫“下一个更大元素 I”，面试里出现的频率相当高。第一次看到这个题的人，99%都会这么写：

vector<int> bruteForce(vector<int>& nums) { int n = nums.size(); vector<int> res(n, -1); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (nums[j] > nums[i]) { res[i] = nums[j]; break; } } } return res; }

代码逻辑非常直白：对每个元素，都往右边扫描，找到第一个比自己大的就停。但问题是，当数组长度是10万级别时，这代码的耗时可能从几十毫秒直接飙到好几秒，在算法题的标准时限下基本就是超时。

1.2 暴力解法到底慢在哪里

暴力解法慢的根本原因在于：信息没有复用。每次找下一个更大元素时，都是从头开始重新扫描，之前已经扫过的比较结果完全没有被利用起来。

举个例子，数组是[5, 4, 3, 2, 1, 6]。暴力解法找元素5的下一个更大元素时，要一路扫到6；找元素4的下一个更大元素时，又要从4开始一路扫到6。这中间其实有一堆重复工作：5、4、3、2、1这五个元素的“右边第一个比自己大的元素”其实全都是6，但暴力方法要为每个元素各扫一遍，重复比较了很多次。

从时间复杂度上看，最坏情况下（比如严格递减的数组），暴力解法要做约n²/2次比较，也就是O(n²)。数组长度到10万，这个量级就是10亿次比较，超时几乎是必然的。

那如果能做到“扫一遍数组就顺手把所有结果算出来”，是不是就舒服多了？单调栈干的就是这件事。

1.3 单调栈的核心思想：把“待处理元素”按顺序押在栈里

单调栈的思想可以这么理解：我一边从左往右遍历数组，一边维护一个栈，这个栈里存的是“还没找到答案的元素下标”，而且栈内元素对应的值保持单调（递增或递减）。每来一个新元素，我就把栈里所有能“被新元素解决”的元素弹出去，给它们记上答案，再把新元素的下标压入栈。

还是用[2, 1, 4, 3]这个例子，找右边第一个更大元素时，我们维护一个“从栈底到栈顶递减”的栈（也就是栈顶元素最小）：

1. 遍历到2：栈空，直接把下标0压栈。栈：[0]
2. 遍历到1：1比栈顶对应的2小，不弹出，压栈。栈：[0, 1]
3. 遍历到4：4比栈顶对应的1大，弹出下标1，答案记为4；再弹下标0，答案记为4；然后下标2压栈。栈：[2]
4. 遍历到3：3比栈顶对应的4小，压栈。栈：[2, 3]

遍历结束，栈里剩下的元素右边没有更大的元素，答案记-1。

这里最关键的一点是，每个元素最多入栈一次、出栈一次，所以总时间是O(n)。这就是单调栈省时间的本质——它把每个元素的比较次数摊还成了常数次，而不是每次都要从头扫。

2. 单调栈的C++实现：模板代码与现实选型

理解了思想，接下来就是动手写代码的问题。C++里实现单调栈，其实有一堆细节值得掰扯，比如用哪个容器、栈里存什么、要不要加哨兵，这些直接决定你的代码是“能跑”还是“好写且不出错”。

2.1 用std::stack还是vector模拟栈

很多第一次接触单调栈的人会直接用std::stack，这完全没问题，逻辑上没毛病。不过我在刷题时更推荐用vector模拟栈，原因有三点：

• 访问栈内元素更灵活：单调栈很多时候不只要看栈顶，比如计算“柱状图中最大的矩形”时，弹出栈顶后需要取新的栈顶作为左边界，std::stack做不到直接看栈里第二个元素，而vector可以。
• 避免不必要的封装开销：std::stack默认底层也是deque，虽然开销通常可以忽略，但vector的连续内存访问更友好，在刷题场景下能省一点是一点。
• 调试更方便：用vector模拟栈时，打印整个栈或者检查栈的内容很容易，直接遍历stk就行，而std::stack只能从栈顶一个个弹出来看，调试体验很差。

所以我建议的模板是：

vector<int> stk; // 用vector模拟栈 stk.push_back(i); // 入栈 stk.back(); // 取栈顶 stk.pop_back(); // 出栈 int topIndex = stk.back();

实际运用中，这套写法比std::stack顺手太多。你甚至可以把stk当成一个特殊的有序数组来理解，很多边界情况一眼就能看穿。

2.2 单调栈的入栈出栈规则：到底谁是“单调递增”

这是一个特别容易混乱的地方，因为网上关于“递增栈”“递减栈”的说法经常互相矛盾，原因在于大家说“递增”时参照的方向不一致。我不纠结名词，直接用“出栈条件”来定义，你只要记住一句话：你想找什么，就用什么条件触发弹出。

• 找右边第一个更大的元素：当前元素nums[i]大于栈顶元素时，栈顶元素的答案就是nums[i]，弹出栈顶。
• 找右边第一个更小的元素：当前元素nums[i]小于栈顶元素时，栈顶元素的答案就是nums[i]，弹出栈顶。

判断条件简单说就是“谁把谁比下去，谁就负责给答案”。我写代码时，只关心 while 循环里那个比较符号是>还是<，具体栈内是单调递增还是单调递减，由这个条件自动决定，不用死记。

2.3 栈里存下标，别存值

很多初学版本会在栈里直接存值，比如[2, 1, 4]就压入2、1、4。这样做对于某些简单题没问题，但一旦题目需要计算“两个元素之间的距离”或者“区间的宽度”，你就抓瞎了。

举个例子，如果题目要求返回的不只是“下一个更大元素的值”，而是“下一个更大元素和自己的距离”（比如“每日温度”这题），那你必须知道下标才能算距离。只存值的话，下标信息就丢了。

我的习惯是：栈里一律存下标，要取值再通过nums[stk.back()]去取。这样做多一道索引转换，但换来的是通用性，无论是求值、求距离还是求区间宽度，都能应付。

2.4 哨兵元素：让边界不再需要特判

单调栈代码里最烦人的就是边界处理：栈空了怎么办？数组遍历完栈里还剩一堆元素怎么办？如果每个分支都去if判断，代码很容易写得又长又容易漏。

一个非常实用的技巧是往原数组里加“哨兵”。比如“柱状图中最大的矩形”这题，我们可以在数组最前面和最后面各插入一个高度为0的柱子。前面加0，保证栈永远不会真正空到没法计算左边界；后面加0，保证遍历结束后，栈里所有柱子都会被强制弹出并计算结果。

我后面讲具体题目时会给出对应代码，这里先提一句：哨兵的本质是“用一个虚构的极值元素，触发最后一次全场结算”。想明白这一点，很多边界问题的特判都会自动消失。

3. 四道经典题拆解：从模板到变形

光有模板不够，得在真实题目里体会“怎么套”“怎么变形”。我挑了四道比较有代表性的题，从易到难，把单调栈的用法拆开揉碎讲一遍。

3.1 每日温度：从“找值”到“找距离”

题目要求是：给定一个温度数组，对每一天，输出还需要等多少天才能等到一个更高的温度。比如[73, 74, 75, 71, 69, 72, 76, 73]，答案是[1, 1, 4, 2, 1, 1, 0, 0]。

这题和“下一个更大元素”几乎一模一样，只不过返回的不是那个更大的元素，而是“距离”。因此，栈里存下标这个习惯就派上用场了：

vector<int> dailyTemperatures(vector<int>& temperatures) { int n = temperatures.size(); vector<int> ans(n, 0); vector<int> stk; // 存下标，栈内温度从栈底到栈顶递减 for (int i = 0; i < n; i++) { while (!stk.empty() && temperatures[stk.back()] < temperatures[i]) { int prev = stk.back(); stk.pop_back(); ans[prev] = i - prev; // 距离 = 当前下标 - 历史下标 } stk.push_back(i); } return ans; }

这段代码的关键就是ans[prev] = i - prev。因为栈里存的是下标，所以一减就能得到天数。如果存的是值，这里就得回头遍历数组找下标，麻烦不说，还可能搞错。栈里最终剩下的那些下标，说明右边没有更高的温度，ans初始化就是0，正好不用管。

这个题算是单调栈的“最小完整实现”，我建议先把这个代码背熟、吃透，再去碰更复杂的题目。

3.2 柱状图中最大的矩形：哨兵技巧的最佳示范

这题我愿称之为单调栈的“必修课”，因为它的解题过程能把单调栈的潜力完全释放出来。题目是：给定一个数组heights，每个值代表一根柱子的高度，求这些柱子能组成的最大矩形面积。

思路是：遍历每一根柱子，把每根柱子当作矩形的高，往左右两边扩展，直到遇到比它矮的柱子为止，然后计算宽度乘高度，取最大值。暴力做法是对每根柱子往左右分别扫描，O(n²)。用单调栈可以做到O(n)：栈里存柱子下标，维持从栈底到栈顶递增（即栈顶柱子最矮)。每当遇到一根柱子比栈顶柱子矮时，说明栈顶柱子的“右边界”出现了，此时弹出栈顶，计算以它为高的矩形面积，而新的栈顶就是它的“左边界”。

这里哨兵就非常有用。来看代码：

int largestRectangleArea(vector<int>& heights) { heights.insert(heights.begin(), 0); // 左哨兵 heights.push_back(0); // 右哨兵 int n = heights.size(); vector<int> stk; int ans = 0; for (int i = 0; i < n; i++) { while (!stk.empty() && heights[stk.back()] > heights[i]) { int h = heights[stk.back()]; stk.pop_back(); int w = i - stk.back() - 1; ans = max(ans, h * w); } stk.push_back(i); } return ans; }

左哨兵0的作用是：当栈里所有真实柱子都被弹出后，左边界还有一个下标0的虚拟柱子兜底，这样stk.back()不会越界。右哨兵0的作用更关键：它保证了遍历到最后，所有还没被弹出的柱子都会因为“0比它们矮”而进入 while 循环，完成面积计算，不用再额外写收尾代码。

我当年第一次做这题时，没加哨兵，写了一堆if (stk.empty())的特判，结果又长又容易错。后来理解了哨兵的思路，代码直接清爽了不止一个量级。这是我在单调栈里学到的性价比最高的一招。

3.3 接雨水：单调栈与区间积水计算

“接雨水”是另一道很经典的题。给定一个非负整数数组表示柱子的高度，计算下雨之后能接多少雨水。这题有很多解法，双指针、动态规划都能做，但用单调栈也有一个非常自然的视角。

思路是：从左往右遍历，维护一个从栈底到栈顶递减的栈（栈顶最矮）。当遇到一根柱子比栈顶柱子高时，说明栈顶这根柱子可以和新的柱子形成一个“凹槽”，此时弹出栈顶，以它为底部，计算这个凹槽能接的水量。

int trap(vector<int>& height) { int n = height.size(); vector<int> stk; int ans = 0; for (int i = 0; i < n; i++) { while (!stk.empty() && height[stk.back()] <= height[i]) { int bottom = height[stk.back()]; stk.pop_back(); if (stk.empty()) break; // 没有左边界，接不了水 int left = stk.back(); int w = i - left - 1; int h = min(height[left], height[i]) - bottom; ans += w * h; } stk.push_back(i); } return ans; }

我学这题时有一个很大的顿悟：单调栈其实是在“按层”计算水量。弹出栈顶柱子作为底部后，水的高度取决于左右两边较矮的那一根，再减去底部高度，乘以宽度。每一次弹出，算的是以当前底部柱子的高度为下限的一层水。一层一层加起来，总水量就出来了。

这个题也是理解“为什么弹出后要取新栈顶作为左边界”的最佳例子。新栈顶虽然不是空间上紧挨着的左邻居，但在“高度关系”上，它是当前凹槽真正起阻挡作用的那根柱子。

3.4 循环数组与删除类题目：单调栈不只是“下一个更大”

单调栈的题目远不止“找下一个更大元素”这一种。比如处理循环数组时，我们可以把原数组“虚拟地”重复一遍，做法是用下标i从0遍历到2n-1，实际访问数组时用i % n。这样每个元素会被访问两次，后一轮访问时就能看到“循环意义下的下一个更大元素”。LeetCode 503这题就是典型代表。

还有一类题目看起来和“找更大元素”关系不大，但本质也用到单调栈的思想，比如“去除重复字母”和“移掉K位数字”。这类题的思路是：从左往右扫描，用一个栈维护结果，当栈顶元素大于当前元素、且栈顶元素在后续还可以出现时，就把它弹出，因为它会让字典序变得更大。这维护的其实就是一个“单调递增栈”，只是弹出条件里多了一个“后续是否还有机会”的判断。

拿“移掉K位数字”来说，核心代码是这样的：

string removeKdigits(string num, int k) { vector<char> stk; for (char c : num) { while (!stk.empty() && k > 0 && stk.back() > c) { stk.pop_back(); k--; } stk.push_back(c); } while (k > 0) { stk.pop_back(); k--; } // 去掉前导0 int start = 0; while (start < stk.size() && stk[start] == '0') start++; string res(stk.begin() + start, stk.end()); return res.empty() ? "0" : res; }

这类题的价值在于告诉你：单调栈的“单调性”是一种维护有序候选集合的通用方法。遇到“要选出字典序最小”或“要在线维护一个局部最优序列”的问题时，都可以考虑用这个思路。

4. 实战中踩过的坑与排查手法

算法思路讲完，接下来是真正的“血泪教训”时间。这些坑我在刷题时几乎一个不落全踩过，如果你能在第一次接触单调栈时就知道它们，至少能省掉好几小时的排查时间。

4.1 等值元素：弹出还是保留

这是最容易被忽略的细节。处理“下一个更大元素”时，如果当前元素等于栈顶元素，要不要弹出栈顶？答案是：不要弹，直接压栈。

比如数组[3, 3]，求右边第一个更大的元素。如果用>=作为弹出条件，遍历到第二个3时会把第一个3弹出去，然后给它的答案记为第二个3的值，也就是3。但“第一个比3大的元素”应该是严格大于3的元素，第二个3只是等于它，不应该算作答案。正确的做法是用>作为弹出条件，等于时不弹。

反过来，在“接雨水”这类题里，我用的是<=弹出。为什么？因为水面高度取决于左右的较小值，如果左右高度相等，把它当成底部来算，水量是0，不影响结果，还能顺便减少栈内重复元素。所以在实际做题时，到底用>还是>=，必须根据题目的语义决定，这是我反复提醒自己的第一条。

4.2 循环数组处理时的取模隐患

循环数组题里，如果遍历2n次，下标i % n取到同一个元素两次，第二次访问时该元素还没被弹出去，就可能出现重复计算或者死循环的隐患。我的经验是：循环数组场景下，出栈条件最好保持和处理普通数组时完全一致，只在入栈前判断当前是不是“第一轮”的下标。

最常见的写法是：

for (int i = 0; i < 2 * n; i++) { int idx = i % n; while (!stk.empty() && nums[stk.back()] < nums[idx]) { ans[stk.back()] = nums[idx]; stk.pop_back(); } if (i < n) stk.push_back(i); // 只把第一轮的下标压栈 }

如果不加if (i < n)，第二轮会把相同的下标再压一次，虽然有时结果碰巧对，但逻辑上是有问题的。我第一次写循环数组题时没加这个判断，结果在特殊用例上答案全乱了。所以这句if (i < n)不要省。

4.3 栈空和越界问题

用vector模拟栈，最容易崩的地方就是stk.back()之前忘了判空。尤其是“接雨水”这类题，弹出栈顶后要立刻判断栈是否为空，因为如果没有左边界，这个凹槽是漏的，接不住水。

一个通用的防护思路是：在脑子里把“栈空”当成一种特殊的边界状态，每次执行stk.back()前先问自己一句“现在栈真不可能是空的吗”。如果答案是“不确定”，就老老实实加一个!stk.empty()的判断。虽然很多人觉得判空很麻烦，但单调栈的题目里，判空多写几次，只会有好处，不会有坏处。

4.4 调试单调栈的三种有效手段

单调栈的逻辑不像普通遍历那么容易一眼看出错，所以我一般用三种手段排查：

第一，打印栈内所有元素。因为用vector模拟栈，所以直接遍历打印stk的每一个值，配合当前遍历到的数组下标，可以直观看到每一步入栈出栈是否正常。用std::stack就没有这么方便，这也是我坚持用vector的原因之一。

第二，构造小规模用例手跑一遍。比如[2, 1, 4, 3]、[3, 3, 3]、[5, 4, 3, 2, 1]，这些极端用例能快速暴露等值处理和单调方向的问题。我遇到Bug时，第一件事不是瞪着眼睛看代码，而是拿这些用例自己模拟一遍入栈出栈过程，往往很快就能定位到问题在哪。

第三，对比暴力解法。写单调栈时同时留一个暴力解法的函数，在小数组上对拍，输出不一致的地方就是Bug所在。这个习惯帮我抓出过不少边界上的隐藏问题，强烈推荐给刚开始接触这类算法的朋友。

5. 怎么判断一道题该不该用单调栈

学完原理和题型，最后一个问题可能最实际：拿到一道新题，怎么知道用不用单调栈？我的判断标准其实就三句话。

5.1 三个自检问题

第一，题目里有没有“下一个更大/更小元素”这样的字眼？或者更隐晦的表述，比如“右边第一个比它高的”“左边第一个比它小的”。有这类描述，单调栈就是第一候选。

第二，是不是需要“在线维护一个区间内的最小值/最大值”？比如“滑动窗口最大值”其实用的是单调队列，但如果问题退化到“左侧最近的最小值”，那单调栈就可以上。这类问题的共性是：我们需要在一个快速变化的候选集合里反复取极值。

第三，题解里是否存在“对每个元素向左右扩展直到遇到边界”的暴力思路？如果有，而且你发现暴力扩展时很多信息被重复计算了，那么用单调栈来缓存这些扩展结果，往往就是正解。

5.2 和单调队列、优先队列的边界在哪里

刚开始学的时候，经常把单调栈、单调队列、优先队列混在一起。我的区分方式很简单：

• 单调栈：处理“单方向、找最近、元素只与自己左右邻居比较”的问题，往往只需要从左到右扫一遍。它回答的是“左边/右边第一个比我大/小的元素是谁”。
• 单调队列：处理“滑动窗口里的极值”问题，队列头尾分别维护窗口两端的淘汰逻辑。它回答的是“当前窗口里的最大值/最小值是什么”。
• 优先队列：处理“全局动态取最大/最小”的问题，不要求元素之间的位置关系，只要求随时拿到当前集合里的极值。

一句话总结：单调栈看重的是“位置关系”，优先队列看重的是“数值大小关系”，单调队列则是两者的结合。把这三个工具的关系理清了，做题时选型就不会犹豫。

我个人学单调栈最大的体会是：它不是一个需要死记硬背的模板，而是一种“用有序栈淘汰无用候选”的思维习惯。真正吃透它之后，再遇到一堆看似无关的题目，你都会慢慢发现它们其实共享同一套底层逻辑。希望这篇内容能帮你跨过那道“看着难、学着乱”的门槛，把这部分知识变成你自己的直觉。