刷LeetCode和准备C面试的时候单调栈几乎是绕不开的一块硬骨头。我第一次接触这东西是在刷每日温度那道题当时用双重循环写了个O(n²)的解法一提交数据稍微大点就超时整个人处于既懵又急的状态。后来把单调栈的原理吃透了才明白这个工具的本质就是一句话每个元素最多入栈一次、出栈一次把暴力扫描的重复劳动压缩成线性代价。这篇博客我想用C把它从头讲透包括它到底在维护什么、为什么能省时间、代码怎么写才能少踩坑再配几道经典题目的完整拆解。不管你是刚入门C算法还是在准备面试阶段想快速掌握高频考点都可以按这个路径把单调栈形成自己的套路。1. 单调栈到底解决了什么问题1.1 先从一道必考题说起假设有这样一个需求给定一个数组对于每一个元素找出它右边第一个比它大的元素。这几乎是单调栈最经典的出场场景LeetCode 496、739 这类题目都是这个模型。直接用暴力思路其实也简单每个位置都往右扫一遍遇到更大的就记录答案并跳出找不到就返回 -1。代码写起来不超过十行vectorint bruteForce(const vectorint nums) { int n nums.size(); vectorint ans(n, -1); for (int i 0; i n; i) { for (int j i 1; j n; j) { if (nums[j] nums[i]) { ans[i] j; break; } } } return ans; }问题在于复杂度。外层 n 个位置内层最坏要走到数组末尾总开销是 O(n²)。当数组长度来到 10 的 5 次方甚至更大时这个解法的耗时就会让你意识到必须换思路。单调栈的意义就在于它能把这类问题拉回到 O(n) 的线性范围这也是它在面试和竞赛里频繁出现的原因。1.2 单调栈维护的单调性是什么单调栈从数据结构上看就是一个普通栈只是栈内元素从栈底到栈顶始终保持单调递增或者单调递减。这句话听起来平淡但实际操作中很多人容易绕晕到底什么时候弹栈栈里放的是值还是下标为了说清楚我用一个简单的生活类比。想象一排人从左到右站好你要找每个人的右边第一个比他高的人。从左边开始一路维护一个候选名单。规则是这样的新来的人如果比名单里最后一个人高那么名单里最后那个人可以出名单了因为他已经等到了答案继续往前比直到名单为空或者新来的人不再高于名单末尾的那个人此时新来的人自己也加入名单因为他还在等一个比他更高的后来者。这里面有个关键感觉名单里会留下的人身高从底到顶是递减的因为一旦出现一个更高的人他先把矮的弹走然后自己站上去。于是你可以发现单调这个词描述的其实是候选集合的淘汰顺序而不是答案本身。C 代码里我们通常让栈内存放下标比较的时候用nums[stack.top()]去取真实的值这样既保留了单调性的判断依据又保留了后续计算距离所需的索引信息。1.3 复杂度为什么是 O(n)单调栈的复杂度分析是整个算法最漂亮的部分。虽然我们可能在一个新元素到来时连续弹出很多元素看起来像是在循环里套了循环但每个元素在整个流程中只会被 push 一次、被 pop 一次这一点决定了所有弹栈操作的次数总和不会超过 n。所以无论 while 循环内弹了多少次把整个遍历过程加起来看总操作量都是 O(n) 量级。再加上每个元素入栈时 O(1) 的开销最终就是严格的线性复杂度。这个分析和其他很多算法不太一样它不需要摊还分析的复杂论证只要抓住入栈出栈各一次这个事实面试时你就能讲得很清楚。2. 从暴力解到单调栈一步一步推导2.1 暴力写法到底慢在哪里暴力写法慢不是因为它对元素做了太多操作而是因为它让很多元素被反复扫描。比如数组里有 100 个元素位置 0 的元素为了找右边第一个更大的可能要看完后面 99 个位置 1 的元素又可能再从 2 一直看到末尾。同一个元素被它左边很多等待答案的位置重复查看这就是典型的重复劳动。这种重复可以靠一种方式避免让数据流动起来而不是让每个位置各自去右边找。从左往右遍历的时候我们天然能看到右边的所有元素问题是这些右边的信息没有被及时传递给左边还在等待答案的位置。单调栈的设计就像一个中转站把还没找到右边更大元素的下标住进栈里每当新元素到来就一次性回答那些已经被它满足的等待者。2.2 用具体例子看单调栈的运转过程我以[73, 74, 75, 71, 69, 72, 76, 73]这个数组为例从左到右走一遍理解弹出时机和答案记录。i0值 73。栈为空直接压入下标 0。i1值 74。74 比栈顶值73大因此下标 0 的答案就是当前位置 1弹出 0压入 1。i2值 75。75 比 74 大弹出 1记录答案 2压入 2。i3值 71。71 不大于 75所以 75 的答案还没出现71 压栈。此时栈底到栈顶是 275、371保持递减。i4值 69。同理69 压栈。栈为 2、3、4。i5值 72。72 比栈顶 69 大弹出 4记录答案 572 也比新的栈顶 71 大弹出 3记录答案 572 不大于 75停止弹出。压入 5。此时栈为 2、5。i6值 76。76 比 72 大弹出 5记录答案 676 比 75 大弹出 2记录答案 6。压入 6。i7值 73。73 不大于 76压入 7。栈为 6、7。从这个过程能总结出一个规律栈始终维持从栈底到栈顶的值递减而每次弹出栈顶的时候当前遍历到的元素就是这个栈顶元素等待的右边第一个更大的值。所以这段代码的核心逻辑不是判断栈顶要不要弹出而是判断当前元素是否足够大能回答栈顶的等待。2.3 C代码模板与运行验证基于上面的分析C 模板可以这样写#include bits/stdc.h using namespace std; // 返回每个位置右边第一个更大元素的下标不存在则为 -1 vectorint nextGreaterElementIndex(const vectorint nums) { int n nums.size(); vectorint ans(n, -1); stackint st; // 栈里存下标 for (int i 0; i n; i) { while (!st.empty() nums[st.top()] nums[i]) { ans[st.top()] i; st.pop(); } st.push(i); } return ans; } int main() { vectorint nums {73, 74, 75, 71, 69, 72, 76, 73}; vectorint ans nextGreaterElementIndex(nums); for (int i 0; i (int)nums.size(); i) { cout nums[i] - (ans[i] -1 ? -1 : nums[ans[i]]) endl; } return 0; }运行这段代码你看到的结果就是 74、75、76、72、72、76、-1、-1和之前手推的一致。如果你是在 VS Code 里配好了 C/C 环境直接用 g 编译运行用 Dev-C 或者 CLion 也一样这段代码没有任何平台特殊性。唯一需要注意的是别用太老的编译器bits/stdc.h这个头文件在 MSVC 环境下并不存在Windows 上如果编译报错把头文件换成iostream、vector、stack三条即可实际工程里也更推荐写明确的头文件。3. 三道经典题带你吃透单调栈3.1 每日温度最常见的入门题LeetCode 739 每日温度要求返回每个位置等待多少天会出现更高温度。它其实不是要返回更大的元素而是要返回两个下标之差。解题时只需要在弹栈时记录i - st.top()而不是记录当前元素的值。代码几乎和模板一模一样class Solution { public: vectorint dailyTemperatures(vectorint temperatures) { int n temperatures.size(); vectorint ans(n, 0); stackint st; for (int i 0; i n; i) { while (!st.empty() temperatures[st.top()] temperatures[i]) { int idx st.top(); st.pop(); ans[idx] i - idx; } st.push(i); } return ans; } };这里有一个很值得注意的细节为什么答案默认值是 0而不是 -1因为题目语义决定了没有更高温度的日子等待天数为 0。所以你在套模板的时候一定要看题目的输出定义不要机械复制默认值。这种改一个细节的练习很有意思它能帮你看清模板里哪些部分是必然的哪些部分是根据题目调整的。3.2 柱状图中最大的矩形哨兵技巧实战LeetCode 84柱状图中最大的矩形。这一题的思考方式比每日温度上了一个台阶。暴力思路是枚举每个柱子作为矩形高度然后向左右扩展找到左边界和右边界计算面积取最大值。复杂度是 O(n²)同样撑不住大数据。单调栈解法要维护一个从栈底到栈顶递增的栈。从左到右遍历每个柱子当遇到比栈顶柱子矮的柱子时说明栈顶柱子的右边界已经出现了因为右边第一次出现比它矮的柱子就是它作为高度的矩形无法再往右扩展的位置。此时弹出栈顶以它为高度矩形的右边界是当前柱子下标 i左边界是弹出后新的栈顶下标宽度是i - st.top() - 1。这里最容易出问题的是边界处理。如果第一个柱子就是最高的它左边没有柱子怎么确定左边界如果遍历完了栈里还剩下一些递增的柱子它们右边的矮柱子一直没出现又该怎么处理解决这些边界问题有一个非常干净的技巧在数组头部和尾部各插入一个高度为 0 的哨兵柱子。头部哨兵保证了每个柱子左侧一定有一个比它矮的参照物尾部哨兵保证了最后那些递增的柱子也能在遍历结束时被强制弹出来因为它们终究会碰到一个高度为 0 的右边界。class Solution { public: int largestRectangleArea(vectorint heights) { heights.insert(heights.begin(), 0); heights.push_back(0); stackint st; int ans 0; for (int i 0; i (int)heights.size(); i) { while (!st.empty() heights[st.top()] heights[i]) { int h heights[st.top()]; st.pop(); int w i - st.top() - 1; ans max(ans, h * w); } st.push(i); } return ans; } };这段代码里有两个细节值得展开。第一个是为什么弹栈条件用而不是。考虑两个高度相等且相邻的柱子如果用左边那个柱子会在遇到右边相等高度的柱子时被弹出然后右边柱子入栈计算矩形宽度时会忽略左边那个相等高度的柱子导致漏算。用严格大于时相等高度的柱子暂时保留等到右边界更明确时再一并处理结果反而正确。第二个细节是宽度计算为什么是i - st.top() - 1而不是i - 弹出栈顶的下标因为我们要的是以当前柱高 h 为高的最大矩形它的左边界是弹出后剩余栈顶的位置而不是被弹出柱子自己的位置。3.3 接雨水单调栈在面积计算中的应用LeetCode 42 接雨水也是一个高频题。按列看、按行看、双指针、前缀最大值各种解法都有。单调栈版本的思路是按凹槽来计算的。核心是维护一个递减栈。从左到右遍历当遇到比栈顶元素高的柱子时栈顶这个位置就形成了一个凹槽的底部当前柱子是凹槽的右墙弹出后的新栈顶是凹槽的左墙。可接的雨水量就是(min(左墙高度, 右墙高度) - 凹槽底部高度) × 凹槽宽度凹槽宽度是右墙下标与左墙下标之间的距离再减 1也就是i - st.top() - 1。class Solution { public: int trap(vectorint height) { stackint st; int ans 0; for (int i 0; i (int)height.size(); i) { while (!st.empty() height[st.top()] height[i]) { int mid st.top(); st.pop(); if (st.empty()) break; // 没有左墙无法形成凹槽 int h min(height[st.top()], height[i]) - height[mid]; int w i - st.top() - 1; ans h * w; } st.push(i); } return ans; } };这里的if (st.empty()) break;非常关键。想象一个单调递减的序列比如[5, 4, 3, 2, 1]在这组数据上执行时每个柱子都会被压栈永远不会弹出因此不会触发面积计算。可如果某个位置弹出栈顶后栈空了说明当前这根高柱子左边没有更高的墙此时形成的不是凹槽而是斜坡形不成积水必须直接跳出内层循环继续处理下一根柱子。相比前面两道题接雨水更强调对几何形状的想象。画图的时候建议把栈里的元素画成柱状图把左墙、凹槽底部、右墙三个位置标出来面积计算就一目了然。4. 单调栈在C中的实现细节和调试技巧4.1 栈里存索引还是存值这是初学者最爱纠结的问题。答案几乎永远是存索引也就是下标。原因很直接很多题目要的是位置关系比如每日温度要求等待几天柱状图最大矩形要求矩形宽度接雨水要求左右墙之间的距离这些都需要通过下标来计算。如果你在栈里只存值弹出的时候虽然知道当前柱子的高度却没有办法计算跨度等于白存。那为什么栈里同时又能判断单调性呢因为 C 的stackT允许通过下标栈顶去访问原始数组。你只需要用nums[st.top()]来取值比较即可。代码里写的是栈内存下标比较的是原数组的值这是个非常关键的心智模型想通了这个很多变形题也就顺手了。4.2 严格单调与非严格单调怎么选单调栈的弹栈条件可以是、、、选哪个完全取决于题目对更大/更小/相等的语义要求。如果题目要求下一个严格更大的元素相等的元素不应该让它出栈所以弹栈条件是nums[st.top()] nums[i])。如果题目要求下一个大于等于当前的值那么相等的元素也要被弹出并记录答案弹栈条件就改成nums[st.top()] nums[i]。同样的道理在递增栈场景里如果要求左边第一个严格更小的元素弹栈条件就用如果允许相等也算更小就改成。刷题时遇到等值元素画一个[1, 3, 3, 2]的数组分别跑两种条件观察哪些元素会在什么时候弹出你就再也不会搞混。这个点也是面试官很喜欢追问的地方因为他能通过你的回答判断你是理解原理还是在背模板。4.3 用 vector 模拟栈和打印调试实际刷题时我经常用vectorint来模拟单调栈而不是直接用std::stackint。原因有两个第一vector的back()、push_back()、pop_back()跟栈的接口语义完全对应写起来没有障碍第二调试的时候vector可以整体打印stack却没有迭代器想看看栈里还剩什么元素就得一遍遍 pop很不方便。vectorint st; st.reserve(n); // 预留空间避免频繁扩容 for (int i 0; i n; i) { while (!st.empty() nums[st.back()] nums[i]) { // 处理栈顶元素 st.pop_back(); } st.push_back(i); }如果你在用std::stack而且想观察中间状态可以把当前栈拷贝一份再打印比如这样写一个辅助函数void debugStack(stackint st, const vectorint nums) { cout stack: ; while (!st.empty()) { cout nums[st.top()] ( st.top() ) ; st.pop(); } cout endl; }这里参数写成按值传的stackint st就是在内部拷贝一份保证原栈不受影响。很多调试效果不佳的案例其实是在循环里顺手打印了栈顶但栈本身在变化打印出来的状态和判断逻辑对不上。用辅助函数把整个栈的快照打印出来定位问题会快很多。4.4 边界条件与空栈处理单调栈代码的崩溃点和高危点绝大多数集中在空栈和边界上。开头最容易犯的错误是while条件里只写了nums[st.top()] nums[i]忘了判断!st.empty()结果在第一次循环或者栈弹空之后访问st.top()直接越界崩溃。正确写法永远是while (!st.empty() ...)而且这个顺序不能颠倒因为代码是从左往右求值的一旦st.empty()为真后面的nums[st.top()]就不会被执行这正是 C 短路求值的特性。边界问题的另一种表现是数组首尾元素。数组开头没有左侧元素数组末尾没有右侧元素它们经常没有答案或者需要特殊默认值。柱状图最大矩形里我们用前后加 0 的方式消除这类讨论接雨水里我们用if (st.empty()) break;来避免没有左墙时错误累加积水。这些处理都来自对几何意义和物理意义的理解而不是死记硬背。5. 单调栈刷题速查与面试经验总结5.1 常见问题快速排查表症状可能原因处理方式编译越界崩溃while 条件未判空加上!st.empty()并放在最前面答案全部是初始默认值遍历方向或弹栈条件写反画图确认是求右边更大还是左边更小等值元素结果不对严格单调与非严格选错按题目严格大于/大于等于确定弹栈条件宽度或距离算错栈里存了值而不是下标改成存下标用nums[st.top()]取值比较首尾位置漏算数组边界未处理考虑哨兵节点或单独处理首尾元素接雨水/最大矩形结果偏小凹槽左墙丢失或宽度公式错误检查弹栈后栈是否为空确认宽度是i - st.top() - 1这张表配合上面的代码基本能覆盖 90% 的入门问题。如果写的解法在提交时出错了先用小数据手动跑一遍看是哪个位置开始不对再对照表格定位特征。5.2 面试现场怎么快速识别单调栈问题面试或者刷题时识别这道题是不是单调栈可以通过几个特征来判断。第一个特征是关键词题目中出现下一个更大/更小元素左边第一个更大/更小最大矩形面积接雨水这些表述时优先往单调栈方向思考。第二个特征是数据规模如果数组长度给到10^5量级而你又想到了 O(n²) 的双重循环解法基本可以判断面试官在诱导你使用线性数据结构。第三个特征是题意存在明显的左右双向扩散比如要计算每个位置左右最近更小值的边界这类需求几乎是单调栈的特种签名。确认方向后先不要急着写代码。先问自己三个问题第一我要求的是左边界还是右边界第二栈应该保持递增还是递减第三遇到相等元素时该不该弹出。这三个问题想清楚了代码骨架其实已经固定了剩下只是往里面填业务逻辑。5.3 单调栈还能和哪些算法组合使用单调栈并不是孤立存在的它在实际题目里经常和前缀和、二分、动态规划等套路组合出现。比如 LeetCode 907 子数组的最小值之和需要利用单调栈找到每个元素作为最小值的最远左右边界然后配合前缀和思想统计子数组数量这题就是把单调栈和计数问题结合在一起。再比如有人提到 C 里的快速幂、分治、前缀和这些基础算法它们和单调栈并不冲突一道复杂的综合题完全可以出现先算前缀数组再对某个维度用单调栈求极值区间的组合。更深入一点单调栈和笛卡尔树有非常紧密的关系。笛卡尔树的构造过程本质上就是对一个数组做单调栈扫描每次弹出栈顶时建立节点之间的父子关系。如果你之后想学线段树、可持久化结构或者更复杂的几何问题理解单调栈能帮你顺利过渡到笛卡尔树这个模型。不过这些属于进阶内容基础阶段先把上面三道题吃透已经足够应付大多数面试和竞赛需求。我个人在实际操作中的体会是单调栈最难的地方永远不是不知道模板怎么写而是明明写了模板却不知道自己写的这个模板到底在维护什么。我见过不少同学能默写每日温度的代码但问他为什么要存下标不存值就卡住了。所以在刷题的时候建议你每写完一题都把栈的中间状态画出来自己给自己讲一遍弹出逻辑。真正过了这一关单调栈哪怕一两年不刷重看代码三分钟也能捡起来。最后再分享一个小技巧面试遇到单调栈题先跟面试官说一句我准备维护一个单调递减栈从左往右扫描弹出时记录答案这句话能把你的思路展示得特别清晰也会让面试官更愿意顺着你的方向往下聊。