企业官网建设流程全解析

1. 单调栈到底是怎么一回事

聊到 C++ 算法学习，单调栈是我一直觉得最值得花一晚上弄清楚的技巧之一。名字听起来唬人，其实它就是栈的一种使用方式——保证栈内元素保持单调性，专门用来求数组中每个元素左边或右边第一个比它大、比它小的位置。很多暴力解法要 O(n^2) 的题，换成单调栈之后直接压到 O(n)，模板还非常固定，属于“背下来就能用”的典型。

我最早接触它是刷 LeetCode 的时候，看到“下一个更大元素”“每日温度”这类题，第一反应就是双重循环。后来发现数据规模一上来，双重循环根本跑不动，而单调栈几乎是这类题的唯一正解。这篇内容我按自己的学习路径整理：先讲清楚原理，再给一份可以直接抄的 C++ 模板，然后用四道经典题把模板吃透，最后聊聊我踩过的坑和判断思路。适合刚学完栈和队列、准备进阶数据结构，或者面试前想快速复习的同学，有基础的人也可以直接跳到第三节看题。

1.1 它解决什么问题

先说人话版本。假设你有一排数字，想知道每个数字右边第一个比它大的数是谁。最朴素的做法是两层循环：对每个位置 i，从 i+1 往后扫，找到第一个大于 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; vector<int> nextGreaterElement(const vector<int>& nums) { int n = (int)nums.size(); vector<int> ans(n, -1); stack<int> 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 模拟栈，性能更好 vector<int> 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 和 nums2，nums1 是 nums2 的子集，要求输出 nums1 中每个元素在 nums2 中下一个更大元素的值。

这题的做法分两步：先用单调栈对 nums2 做一遍预处理，得到每个位置的下一个更大元素，存进哈希表；再遍历 nums1 查表输出即可。两步的时间复杂度都是 O(n)，核心代码如下：

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) { unordered_map<int, int> mp; vector<int> 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]。

这题的本质和“下一个更大元素”一模一样，只是返回的不是“更大的值”，而是“更大的值的下标差”。

vector<int> dailyTemperatures(vector<int>& temperatures) { int n = temperatures.size(); vector<int> ans(n, 0); vector<int> 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(vector<int>& heights) { // 前后各补一个高度为 0 的哨兵，统一处理边界 heights.insert(heights.begin(), 0); heights.push_back(0); int n = heights.size(); vector<int> 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(vector<int>& height) { int n = height.size(); vector<int> 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 取真实下标，其余逻辑和基础模板完全一致：

vector<int> nextGreaterElements(vector<int>& nums) { int n = nums.size(); vector<int> ans(n, -1); vector<int> 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，后续所有边界判断都不需要特判了。

我把常见的边界条件整理成一张速查表，方便面试前快速过一遍：

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(vector<int> arr) { int n = arr.size(); vector<int> left(n), right(n); vector<int> 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 分钟，想不出再看题解，看完后必须关掉题解亲手重写一遍。我见过很多人的问题是“看懂了但写不出来”，就是因为缺少重写这一步。单调栈的代码虽然短，但它包含了一种“延迟结算”的思考方式，只看不写是建立不了肌肉记忆的。

我个人在实际操作中还有一个体会：学单调栈不要一次性做太多题，一两道入门题之后停两天再回来做进阶题，效果反而好。因为你的大脑需要时间把“弹出即结算”这种模式真正消化成直觉。等你能在看到一道题时下意识判断“这是单调栈能解的”，并且能区分用递增栈还是递减栈，这门技巧就算是真正学会了。