1. 单调栈到底是怎么一回事聊到 C 算法学习单调栈是我一直觉得最值得花一晚上弄清楚的技巧之一。名字听起来唬人其实它就是栈的一种使用方式——保证栈内元素保持单调性专门用来求数组中每个元素左边或右边第一个比它大、比它小的位置。很多暴力解法要 O(n^2) 的题换成单调栈之后直接压到 O(n)模板还非常固定属于“背下来就能用”的典型。我最早接触它是刷 LeetCode 的时候看到“下一个更大元素”“每日温度”这类题第一反应就是双重循环。后来发现数据规模一上来双重循环根本跑不动而单调栈几乎是这类题的唯一正解。这篇内容我按自己的学习路径整理先讲清楚原理再给一份可以直接抄的 C 模板然后用四道经典题把模板吃透最后聊聊我踩过的坑和判断思路。适合刚学完栈和队列、准备进阶数据结构或者面试前想快速复习的同学有基础的人也可以直接跳到第三节看题。1.1 它解决什么问题先说人话版本。假设你有一排数字想知道每个数字右边第一个比它大的数是谁。最朴素的做法是两层循环对每个位置 i从 i1 往后扫找到第一个大于 nums[i] 的值就停下。这个做法的时间复杂度是 O(n^2)遇到一万个元素就基本卡死了。单调栈的思路是一边遍历数组一边维护一个“从栈底到栈顶单调递增或递减”的栈。每当新元素进来时我们循环弹出栈顶直到栈顶元素满足单调性为止。关键在于每次弹出操作发生时我们刚好能回答“被弹出元素的问题”。这个思路用一句话概括当一个新元素把栈顶元素挤出去时挤它的这个新元素就是栈顶元素要找的答案。比如求“右边第一个更大的元素”栈从栈底到栈顶保持递增新元素比栈顶大那么新元素就是栈顶右侧第一个更大的值。整个过程每个元素最多进栈一次、出栈一次总复杂度 O(n)。1.2 单调递增和单调递减到底谁是递增这是新手最容易绕晕的地方因为大家对“单调递增栈”的理解经常分裂。我先给出一个统一的约定后面所有代码都按这个约定来。所谓的“单调递增栈”指的是从栈底到栈顶元素的值依次递增也就是说栈顶元素是当前栈里最小的那个。反之“单调递减栈”就是栈底到栈顶递减栈顶是最大的。求右边或左边第一个比当前元素大的值用单调递增栈。因为大元素会把小元素挤出去小元素出栈时记录答案。求右边或左边第一个比当前元素小的值用单调递减栈。柱状图中最大矩形这类“找左右两侧边界”的题通常用单调递增栈。接雨水这类“找两侧都比自己高的凹槽”的题用单调递减栈。我建议不要死记题目类型而是记住一句话你希望满足什么条件时结算答案就维护能让那个条件触发的栈。大元素挤走小元素触发的是“找更大元素”的结算小元素挤走大元素触发的是“找更小元素”的结算。2. C 模板代码拆解这一节我直接把核心代码写出来然后一行一行解释。以下模板解决的是“下一个更大元素”问题给你一个数组返回每个位置右侧第一个比它大的元素不存在则填 -1。2.1 为什么栈里存下标而不存值很多第一次接触单调栈的人会问栈里直接存元素值不行吗答案是行但基本所有实际问题都会要求你同时知道位置。比如“每日温度”要求输出的是距离而非值本身“柱状图最大矩形”要算的是宽度和高度乘积这些都离不开下标。更关键的是如果只存值遇到重复元素时无法区分到底是哪一个位置被结算。栈里存下标取值得通过 nums[st.top()] 来拿代价几乎可以忽略却能让你同时拿到值和位置两个信息。所以我的习惯是一律存下标没有例外。2.2 核心模板逐行讲解直接上代码这是我最常用的写法#include vector #include stack using namespace std; vectorint nextGreaterElement(const vectorint nums) { int n (int)nums.size(); vectorint ans(n, -1); stackint st; // 单调递增栈栈内存下标 for (int i 0; i n; i) { // 当前元素比栈顶元素大说明栈顶的“下一个更大元素”找到了 while (!st.empty() nums[i] nums[st.top()]) { ans[st.top()] nums[i]; // 结算栈顶 st.pop(); } st.push(i); // 当前下标入栈 } // 遍历结束后还在栈里的元素说明右侧没有更大值保持 -1 return ans; }拆开看几个关键点第一while 循环的条件用 还是 决定了单调性是否“严格”。用 时相等元素不会弹出栈顶栈内允许存在相等值这是非严格单调用 时相等元素会挤掉旧元素是严格单调。多数“第一个更大”的题用 就够但有些题对相等元素有特殊要求后面说。第二结算动作发生在弹出之前。我们把栈顶下标取出来ans[st.top()] nums[i]然后再 pop。这个顺序不能反过来否则下标就丢了。第三不需要在循环结束后再处理栈内剩余元素。因为 ans 初始化为 -1剩下没被结算的说明右边没有更大的值保持默认值即可。2.3 用 std::stack 还是手写数组栈C 里实现单调栈有两种常见方式直接用std::stack或者用 vector 模拟。// 用 vector 模拟栈性能更好 vectorint st; for (int i 0; i n; i) { while (!st.empty() nums[i] nums[st.back()]) { ans[st.back()] nums[i]; st.pop_back(); } st.push_back(i); }std::stack的优点是语义清晰缺点是你无法直接修改栈底以外的元素某些变形场景比如需要访问栈里第二个元素会非常别扭。vector 模拟栈则完全没有这个问题back()就是栈顶加上pop_back()和push_back()代码长度差不多灵活性却高很多。我个人的建议是刷题、竞赛、面试手写代码都用 vector 模拟。它省去了一层封装调试时还能直接把整个栈打印出来看。如果你用的是std::stack真碰到了需要看栈底元素的题目只能在心里骂自己当初为什么图省事。3. 经典题实战四道题吃透单调栈光有模板还不够单调栈这道坎必须用题目来迈。我选了四道覆盖面很全的题它们分别代表了“模板原样用”“稍作变形”“经典难题”“换个场景”四种情况。3.1 下一个更大元素最基础的模板LeetCode 496 是单调栈入门第一题。给定两个数组 nums1 和 nums2nums1 是 nums2 的子集要求输出 nums1 中每个元素在 nums2 中下一个更大元素的值。这题的做法分两步先用单调栈对 nums2 做一遍预处理得到每个位置的下一个更大元素存进哈希表再遍历 nums1 查表输出即可。两步的时间复杂度都是 O(n)核心代码如下vectorint nextGreaterElement(vectorint nums1, vectorint nums2) { unordered_mapint, int mp; vectorint st; for (int x : nums2) { while (!st.empty() x st.back()) { mp[st.back()] x; st.pop_back(); } st.push_back(x); } for (int i 0; i nums1.size(); i) { nums1[i] mp.count(nums1[i]) ? mp[nums1[i]] : -1; } return nums1; }注意这题我偷懒在栈里直接存了值而不是下标因为最后只关心值。这算是少数可以存值的例外但如果你拿不准还是存下标更稳。这里的单调栈同样是非严格递增栈遍历到新元素 x 时弹出所有比 x 小的栈顶弹出去的元素下一个更大元素就是 x。3.2 每日温度改为记录距离LeetCode 739题目是给你每天的气温列表要返回一个列表answer[i] 表示第 i 天之后多久才会遇到更高的气温。比如 [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 st; for (int i 0; i n; i) { while (!st.empty() temperatures[i] temperatures[st.back()]) { ans[st.back()] i - st.back(); st.pop_back(); } st.push_back(i); } return ans; }这个例子很好地说明了“栈里存下标”的优势结算的时候不仅知道答案值还能直接用下标差算出距离。另外可以发现多个连续下降的天气会一直待在栈里直到遇到一个大升温日一次性批量结算。这种“延迟结算最后打包处理”的思想是单调栈的精髓。3.3 柱状图中最大的矩形难点在边界LeetCode 84 是单调栈里比较难的题。给定非负整数数组 heights每个元素代表柱子的高度求能勾勒出的最大矩形面积。核心思路是对于每根柱子以它的高度作为矩形高度找到它左右两边第一个比它矮的柱子那两个柱子之间的范围就是它能延伸的宽度。对每根柱子都算一遍取最大值即可。暴力做法每根柱子向两边扩展是 O(n^2)单调栈可以做到一次遍历求出所有柱子的左右边界。这里需要的是单调递增栈但注意是严格递增——当遇到相同高度的柱子时应该把前面那个弹出去否则计算宽度时会出错。int largestRectangleArea(vectorint heights) { // 前后各补一个高度为 0 的哨兵统一处理边界 heights.insert(heights.begin(), 0); heights.push_back(0); int n heights.size(); vectorint st; int ans 0; for (int i 0; i n; i) { // 严格递增高度相等也弹出 while (!st.empty() heights[i] heights[st.back()]) { int h heights[st.back()]; st.pop_back(); int left st.back(); // 左边第一个更矮的柱子 int right i; // 右边第一个更矮的柱子 ans max(ans, h * (right - left - 1)); } st.push_back(i); } return ans; }弹栈时被弹出的柱子是当前栈顶它的高度记为 h。弹出后新的栈顶 st.back() 就是它左侧第一个比它矮的柱子当前 i 是右侧第一个比它矮的柱子宽度就是 (i - st.back() - 1)。前后补 0 是个实用技巧左侧补 0 确保空栈时 st.back() 不会越界右侧补 0 则能把最后还没结算的柱子全部逼出来。我有一个直观理解方式栈里的柱子高度是递增队列像一排台阶。每当遇到一个更矮的柱子就说明台阶里那些高个子到头了可以结算它们各自能撑起的最大矩形。3.4 接雨水变形应用LeetCode 42给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子能接多少雨水。这道题如果做过前面的题会觉得风格突变因为它用的不是“求更大元素”逻辑而是“求凹槽”逻辑栈的类型也换成了单调递减栈。基本思路雨水存在于凹槽中凹槽就是“左高、中间低、右高”的三元组。遍历时我们维护一个从栈底到栈顶严格递减的栈。当新柱子比栈顶高时弹出栈顶——这个被弹出的柱子就是凹槽底部新的栈顶是左边界当前柱子是右边界。int trap(vectorint height) { int n height.size(); vectorint st; int ans 0; for (int i 0; i n; i) { while (!st.empty() height[i] height[st.back()]) { int bottom st.back(); // 凹槽底部 st.pop_back(); if (st.empty()) break; // 左边没有更高的柱子存不住水 int left st.back(); // 左边界 int right i; // 右边界 int h min(height[left], height[right]) - height[bottom]; int w right - left - 1; ans h * w; } st.push_back(i); } return ans; }请注意这里的高度计算是min(左右边界) - 底部高度因为水要能存住必须左右都比底部高水面高度由较矮的那一侧决定。宽度则是左右边界之间的间隔。这个题最容易漏掉的条件是if (st.empty()) break;——如果左边没有更高的柱子了那这就是一个斜坡而不是凹槽存不了水。单看模板接雨水和下个更大元素好像差不多都是 while 弹出弹出时结算。差别其实就在“弹什么、怎么结算”。下个更大元素结算的是弹出的元素本身接雨水结算的是弹出元素与两侧边界围成的区域。理解了这一层单调栈就算入门了。3.5 更进一步的变形边界与环形数组LeetCode 503 是下一个更大元素的环形数组版本数组可以循环。处理思路是把数组翻倍遍历 2n 个位置用 i % n 取真实下标其余逻辑和基础模板完全一致vectorint nextGreaterElements(vectorint nums) { int n nums.size(); vectorint ans(n, -1); vectorint st; for (int i 0; i 2 * n; i) { int idx i % n; while (!st.empty() nums[idx] nums[st.back()]) { ans[st.back()] nums[idx]; st.pop_back(); } st.push_back(idx); } return ans; }这类题还有一个好处它帮你验证对“数组下标”的理解。环形数组不是真的要复制一份而是用取模模拟绕圈。有些人在这一步会纠结数组越界实际上用 vector 存下标只要保证 st 里的值始终小于 n取 nums[st.back()] 就不会越界。4. 常见问题与调试实录这一节分享一些我的真实踩坑记录。单调栈代码短但往往一个小地方写错整个结果就乱了而且 debug 起来比一般题更难受因为你盯着栈的变化很难一眼看出哪次入栈/出栈出了问题。4.1 最容易踩的三个坑第一个坑是 while 条件方向写反。很多人会把nums[i] nums[st.back()]写成结果弹出逻辑完全反了。我自己的检查方法是在纸上写一个用例比如 [2, 1, 5]手动模拟一遍。如果轮到 5 时弹出栈里的 2说明条件应该是“当前大于栈顶”这个方向。把模板背下来是一种方式但理解了“大元素挤走小元素”后这个条件基本不会写错。第二个坑是下标访问顺序错误。比如栈里存的是下标却忘了用nums[st.back()]而是直接用st.back() nums[i]这种逻辑比较的就是下标和值结果自然全错。另外在弹出后取st.back()时必须先判断栈是否为空。最典型的例子是接雨水里弹出凹槽底部后如果栈空了要 break否则下一行访问 st.back() 会直接未定义行为。第三个坑是相等元素处理不当。在柱状图最大矩形里必须用严格递增相等高度如果不弹出宽度计算就会偏大或偏小。而在下一更大元素里相等元素要不要弹出取决于题目问的是“大于”还是“大于等于”。这个没有统一答案读题时不注意就会出错。4.2 通用调试三板斧我自己遇到单调栈问题卡壳时从来不会盯着代码空想而是按三步走。第一步加调试打印。用 vector 模拟栈的话直接在循环末尾打印 i、栈内容栈内对应值、ans 当前状态。特别注意打印栈内对应值要用nums[st[j]]直接把 st 打出来没用那只是一堆下标。第二步小规模手算对照。选一个 5 到 6 个元素的样例手工走一遍入栈出栈把你手算的结果和程序结果逐项比对。单调栈的麻烦在于一次遍历会同时影响多个元素的答案跳跃式结算不用笔根本跟不上。第三步换哨兵或补边界。很多时候答案是“差一个”这种边界问题就在数组头尾补上特殊值。比如柱状图两端的补 0接雨水也可以补 0后续所有边界判断都不需要特判了。我把常见的边界条件整理成一张速查表方便面试前快速过一遍题目类型栈的单调性相等元素处理哨兵策略下一个更大元素单调递增栈顶最小弹出时用 相等未结算不需要每日温度单调递增栈顶最小弹出时用 相等未结算不需要柱状图最大矩形严格单调递增相等也要弹出头尾补 0接雨水严格单调递减相等时不弹出先入栈可补 0 简化判断环形下一个更大元素单调递增弹出时用 遍历 2n 个位置4.3 怎么判断一道题能不能用单调栈这是一条特别实用的经验几乎能直接套用。当你看到题目描述里出现“左边/右边第一个比它大/小”“区间内最大/最小”“求与两侧边界相关的最值”这些特征时就可以先往单调栈方向想。判断的标准是暴力解法的瓶颈是否在于“每个元素都要向两边扫描寻找边界”。如果是那么单调栈大概率能用因为它正是通过一次遍历把每个元素的左右边界都算出来。判断的依据是时间复杂度如果题目数据范围在 10 的 5 次方以上又不能排序那双层循环基本没戏就要立刻想到单调栈。另外线性数据结构题里还有一对容易混淆的组合单调栈和单调队列。单调栈维护的是栈内元素的单调性适合处理“向左看”和“向右看”的问题单调队列则额外维护了窗口内元素的顺序关系比如滑窗最大值最小值。区分方法是看问题是不是限制在固定窗口内——是就用单调队列没有窗口限制、需要按顺序结算就用单调栈。5. 单调栈的更多玩法与学习建议最后聊一点扩展内容。单调栈模板本身不难但它是很多高级技巧的基石。比如“贡献法”——计算数组中每个元素作为最小值时能影响多少个子数组这类题核心思路就是找到左右第一个更小的元素然后乘一下左右可选范围本质上就是单调栈的应用。5.1 从“栈”到“贡献法”的思路升级举个例子给定一个数组求所有子数组的最小值之和。暴力做法是枚举所有子数组O(n^2)。用贡献法的话对每个元素 a[i]找到左边第一个比它小的位置 L右边第一个比它小或小于等于避免重复的位置 R那么 a[i] 作为最小值的子数组个数就是 (i - L) * (R - i)。再乘以 a[i] 求和就行。左右边界的获取过程就是一次单调栈遍历。这个思路的好处是它把“枚举子数组”转化成了“统计每个元素的贡献”复杂度降到 O(n)。C 里写起来也漂亮long long sumSubarrayMins(vectorint arr) { int n arr.size(); vectorint left(n), right(n); vectorint st; // 左边第一个更小严格更小 for (int i 0; i n; i) { while (!st.empty() arr[i] arr[st.back()]) st.pop_back(); left[i] st.empty() ? -1 : st.back(); st.push_back(i); } st.clear(); // 右边第一个更小小于等于避免重复计数 for (int i n - 1; i 0; --i) { while (!st.empty() arr[i] arr[st.back()]) st.pop_back(); right[i] st.empty() ? n : st.back(); st.push_back(i); } long long ans 0; for (int i 0; i n; i) { ans (long long)(i - left[i]) * (right[i] - i) * arr[i]; } return ans; }注意右边的条件我用了 这是因为相等的元素如果在两边都算“更小”同一个子数组会被重复计数。通常的处理办法是左边取严格更小右边取小于等于这样每个子数组的最小值只会被最右边的那个最小值元素统计到一次。这种对称但不对称的处理方式是这类题的精髓背下来但不理解的话很容易在面试现场被追问卡住。5.2 C 实现的一些实用技巧用 C 写单调栈我一般保持三个习惯。第一使用 vector 模拟栈并将此作为固定范式。理由前面说过灵活且便于调试。vector 的 reserve 可以先分配好空间减少多次扩容带来的开销。第二如果能用数组下标就尽量别用迭代器或栈对象。刷题环境里图快但工程化的代码里用std::stack没问题只是碰到需要随机访问栈元素的场景会受限。因此 C 里我很少在单调栈类题目中用真正的 stack。第三注意类型溢出。算宽度乘以高度、子数组个数乘以值时int 很容易溢出尤其 LeetCode 这类平台会把数据范围设到 10 的 9 次方。算面积、算数量的地方习惯性用 long long哪怕题目样例没到那个量级也先写了。5.3 学习路线建议如果你正在学 C 并且刚接触单调栈我建议按这个顺序走先手写数组模拟栈理解 push 和 pop 底层发生了什么然后做当前元素与栈顶元素的比较逻辑再做“下一个更大元素”和“每日温度”这两道入门题接着挑战柱状图和接雨水最后去处理环形数组和贡献法的题。刷题时给自己设一个时间限制比如每道题先独立思考 30 分钟想不出再看题解看完后必须关掉题解亲手重写一遍。我见过很多人的问题是“看懂了但写不出来”就是因为缺少重写这一步。单调栈的代码虽然短但它包含了一种“延迟结算”的思考方式只看不写是建立不了肌肉记忆的。我个人在实际操作中还有一个体会学单调栈不要一次性做太多题一两道入门题之后停两天再回来做进阶题效果反而好。因为你的大脑需要时间把“弹出即结算”这种模式真正消化成直觉。等你能在看到一道题时下意识判断“这是单调栈能解的”并且能区分用递增栈还是递减栈这门技巧就算是真正学会了。