第一次认真学单调栈是因为我在刷一道非常经典的题时被卡住了给定一个数组要求求出每个元素右边第一个比它大的数。我当时第一反应是暴力两重循环代码倒是三分钟写完了一提交直接超时。后来在讨论区看到有人提到“单调栈”三个字说实话当时觉得这名字挺吓人的感觉像是什么高深的数据结构。真正花了一个周末把它啃下来之后才发现单调栈的思想一点都不复杂本质上就是一个“有原则地维护栈内有序性”的普通栈只是这个“原则”用对了地方能把很多O(n²)的问题直接压到O(n)。这篇内容就是我想把当时踩过的坑、总结出来的套路以及C实现时的细节一次性讲清楚。无论你是刚接触算法的初学者还是准备面试想快速复习这部分内容的开发者只要能看懂数组和栈的基本操作这篇文章应该能让你少走不少弯路。我会从暴力解法的痛点开始讲一步步拆解单调栈的原理、C代码模板、四类经典题型以及我在实际刷题过程中遇到的那些“没写在题解里”的坑。1. 为什么需要单调栈先从暴力解法的痛点说起单调栈这东西很多人一上来就背模板结果换个题目就不会用了。我觉得问题恰恰出在“只知道模板长什么样不知道模板要解决什么问题”。所以我先把问题源头讲透。1.1 一个再常见不过的题目场景先看这个最经典的场景给定一个整数数组对数组中的每一个元素找出它右边第一个比它大的元素如果不存在就返回-1。比如数组是[2, 1, 4, 3]那么答案是[4, 4, -1, -1]。这个题在LeetCode上的名字叫“下一个更大元素 I”面试里出现的频率相当高。第一次看到这个题的人99%都会这么写vectorint bruteForce(vectorint nums) { int n nums.size(); vectorint 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]这个例子找右边第一个更大元素时我们维护一个“从栈底到栈顶递减”的栈也就是栈顶元素最小遍历到2栈空直接把下标0压栈。栈[0]遍历到11比栈顶对应的2小不弹出压栈。栈[0, 1]遍历到44比栈顶对应的1大弹出下标1答案记为4再弹下标0答案记为4然后下标2压栈。栈[2]遍历到33比栈顶对应的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只能从栈顶一个个弹出来看调试体验很差。所以我建议的模板是vectorint 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]。这题和“下一个更大元素”几乎一模一样只不过返回的不是那个更大的元素而是“距离”。因此栈里存下标这个习惯就派上用场了vectorint dailyTemperatures(vectorint temperatures) { int n temperatures.size(); vectorint ans(n, 0); vectorint 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(vectorint heights) { heights.insert(heights.begin(), 0); // 左哨兵 heights.push_back(0); // 右哨兵 int n heights.size(); vectorint 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(vectorint height) { int n height.size(); vectorint 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) { vectorchar 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 和单调队列、优先队列的边界在哪里刚开始学的时候经常把单调栈、单调队列、优先队列混在一起。我的区分方式很简单单调栈处理“单方向、找最近、元素只与自己左右邻居比较”的问题往往只需要从左到右扫一遍。它回答的是“左边/右边第一个比我大/小的元素是谁”。单调队列处理“滑动窗口里的极值”问题队列头尾分别维护窗口两端的淘汰逻辑。它回答的是“当前窗口里的最大值/最小值是什么”。优先队列处理“全局动态取最大/最小”的问题不要求元素之间的位置关系只要求随时拿到当前集合里的极值。一句话总结单调栈看重的是“位置关系”优先队列看重的是“数值大小关系”单调队列则是两者的结合。把这三个工具的关系理清了做题时选型就不会犹豫。我个人学单调栈最大的体会是它不是一个需要死记硬背的模板而是一种“用有序栈淘汰无用候选”的思维习惯。真正吃透它之后再遇到一堆看似无关的题目你都会慢慢发现它们其实共享同一套底层逻辑。希望这篇内容能帮你跨过那道“看着难、学着乱”的门槛把这部分知识变成你自己的直觉。