当前位置：首页 > news >正文

C++算法之单调栈

news 2025/7/29 7:24:58

C++算法中的单调栈：从入门到实战指南

大家好！今天我们来聊聊C++算法中一个超级实用的工具——单调栈。别被名字吓到，它其实很简单，就像排队买奶茶一样：队伍总是从矮到高（或从高到矮）排得整整齐齐，这样处理问题时就特别高效。在算法面试里，单调栈是高频考点，LeetCode上很多难题（比如找“下一个更大元素”或算“柱状图最大面积”）都能用它轻松搞定。这篇文章，我会用接地气的语言，带大家一步步理解单调栈的原理、C++实现和应用。全程10000字以上，保证干货满满，读完你就能上手写代码！

一、引言：为什么单调栈这么牛？

想象一下，你在超市排队结账。如果队伍乱七八糟，收银员得花时间找谁先来谁后到，效率贼低。但如果队伍按身高排好（比如从矮到高），收银员一眼就能看出顺序，处理速度飞快。单调栈就是这个道理：它是个栈（后进先出的数据结构），但里面的元素保持单调递增或递减的顺序。这样处理数组问题时，能省下大量时间。

在C++算法中，单调栈为啥重要？首先，它能把时间复杂度从$O(n^2)$降到$O(n)$，空间复杂度也常是$O(n)$，这在处理大数据时救命啊！其次，接地气地说，它就像你的“算法瑞士军刀”——专治各种“找邻居元素”的毛病。比如：

找数组中每个元素的下一个更大元素（Next Greater Element）。
算柱状图中最大矩形面积（LeetCode经典题）。
优化动态规划问题，避免重复计算。

别担心，我会用生活例子贯穿全文。比如，把数组元素想象成排队的人的身高，单调栈就是智能排队系统。准备好了吗？我们开整！

二、单调栈的基本概念：到底是个啥？

单调栈，顾名思义，就是栈内元素保持单调性（monotonic）。分两种类型：

单调递增栈：栈中元素从底到顶递增，就像排队时从矮到高。数学上，如果栈底元素是$a$，栈顶是$b$，那么$a \leq b$。
单调递减栈：栈中元素从底到顶递减，排队时从高到矮，即$a \geq b$。

为啥要单调？核心是利用单调性快速跳过无效比较。举个例子，假设数组是[2, 1, 4, 3]，我们要找每个元素的“下一个更大元素”。用单调递减栈：

遍历到2：栈空，直接入栈。
遍历到1：1 < 2（栈顶），入栈（栈：[2,1]）。
遍历到4：4 > 1（栈顶），弹出1，记录1的下一个更大是4；4 > 2，弹出2，记录2的下一个更大是4；栈空，4入栈。
遍历到3：3 < 4，入栈（栈：[4,3]）。结果：2→4, 1→4, 4→无, 3→无。看，只用一次遍历就搞定！

数学上，单调栈的单调性可以用不等式描述。对于单调递增栈，任意两个元素$s_i$和$s_j$（$i < j$），满足： $$s_i \leq s_j$$ 类似地，单调递减栈满足： $$s_i \geq s_j$$ 这种结构让查找、插入、删除操作高效，时间复杂度通常是$O(n)$，因为每个元素只入栈出栈一次。

接地气理解：把它当成一个“智能过滤器”。数组元素一个个进来，栈自动踢掉不满足单调性的“弱者”，只留“强者”。这样，问题就简化了！

三、单调栈的工作原理：一步步拆解

现在，我们深入看看单调栈怎么工作。我会用找“下一个更大元素”（Next Greater Element）这个经典问题演示，接地气地说，就是“为每个人找右边第一个比他高的朋友”。

算法步骤（以单调递减栈为例）：

初始化：创建一个空栈，用于存放数组索引（不是值，索引更方便）。
遍历数组：从左到右处理每个元素。
比较与弹出：如果当前元素 > 栈顶元素，说明栈顶元素找到了“下一个更大”（就是当前元素），弹出栈顶并记录结果。
入栈：当前元素入栈（保持栈的单调递减）。
收尾：遍历完后，栈中剩余元素没有“下一个更大”，记为-1或特定值。

伪代码更直观：

function nextGreater(arr):stack = empty stackresult = array of size n, initialized to -1for i from 0 to n-1:while stack not empty and arr[i] > arr[stack.top()]:index = stack.pop()result[index] = arr[i]  // 找到下一个更大stack.push(i)return result

实例演示：数组 [3, 1, 4, 2]

步骤1：i=0, 元素3。栈空，入栈（栈：[0]）。
步骤2：i=1, 元素1。1 < 3（栈顶值），入栈（栈：[0,1]）。
步骤3：i=2, 元素4。4 > 1（栈顶值），弹出索引1，记录result[1]=4；4 > 3，弹出索引0，记录result[0]=4；栈空，入栈（栈：[2]）。
步骤4：i=3, 元素2。2 < 4，入栈（栈：[2,3]）。
结束：栈中剩余索引2和3，result[2]=-1, result[3]=-1。结果：[4, 4, -1, -1]。完美！

为什么高效？时间复杂度$O(n)$，因为每个元素只入栈一次、出栈一次。空间复杂度$O(n)$，栈最多存n个元素。

接地气技巧：想象栈是个“候车室”，元素进来等“更大元素”出现。如果等到了，就离开；否则，一直等下去。单调性保证候车室不会乱。

四、C++实现：手把手教你写代码

理论懂了，来点实战！我用C++实现一个完整的单调栈应用——解决“下一个更大元素”问题。代码尽量简洁，加详细注释，接地气解释。

完整C++代码

#include <iostream>
#include <vector>
#include <stack>
using namespace std;// 函数：找到数组中每个元素的下一个更大元素
vector<int> nextGreaterElement(vector<int>& nums) {int n = nums.size();vector<int> result(n, -1);  // 初始化结果数组，默认-1表示无更大元素stack<int> st;  // 用栈存索引，保持单调递减// 遍历数组for (int i = 0; i < n; i++) {// 当栈不空且当前元素大于栈顶元素时，说明栈顶元素找到了"下一个更大"while (!st.empty() && nums[i] > nums[st.top()]) {int topIndex = st.top();  // 获取栈顶索引st.pop();  // 弹出栈顶result[topIndex] = nums[i];  // 记录结果}st.push(i);  // 当前元素入栈（索引）}return result;
}int main() {// 测试用例vector<int> arr = {3, 1, 4, 2};vector<int> result = nextGreaterElement(arr);// 输出结果cout << "原数组: ";for (int num : arr) cout << num << " ";cout << "\n下一个更大元素: ";for (int res : result) cout << res << " ";return 0;
}

代码详解（接地气版）

头文件：#include <stack> 引入栈，#include <vector> 用动态数组。
nextGreaterElement函数：
- vector<int> result(n, -1): 创建结果数组，初始-1（没找到更大元素）。
- stack<int> st: 栈存索引，不是值。为啥？因为索引能定位元素，值比较时直接用nums[i]。
- 遍历循环：for (int i = 0; i < n; i++) 逐个处理元素。
- while条件：!st.empty() && nums[i] > nums[st.top()] – 栈不空且当前元素大于栈顶元素？那就弹出栈顶并记录。
- 入栈：st.push(i) – 当前索引入栈，保持栈的单调递减。
main函数：测试数组[3,1,4,2]，输出结果[4,4,-1,-1]。

编译运行（用g++）：

g++ -o monotonic_stack monotonic_stack.cpp
./monotonic_stack

输出：

原数组: 3 1 4 2 
下一个更大元素: 4 4 -1 -1

为什么这样写？

用索引存栈：避免值重复问题，比如数组有相同元素时。
单调递减栈：适合找“下一个更大”；如果找“下一个更小”，就用单调递增栈。
边界处理：数组为空时，代码也能处理（n=0，直接返回）。

接地气调试：加打印语句看栈变化。例如，在while循环里加cout << "弹出索引: " << topIndex << endl;，观察执行过程。

五、应用场景：单调栈能解决哪些问题？

单调栈不是花架子，它在算法题中超级实用。下面列举几个接地气的经典应用，全部来自LeetCode，我给出问题描述、解法思路和C++代码片段。

1. LeetCode 496: Next Greater Element I（简单题）

问题：给定两个数组nums1和nums2，nums1是nums2的子集。找到nums1中每个元素在nums2中的下一个更大元素。
解法：先用单调栈处理nums2，得到每个元素的下一个更大；然后用哈希表存结果，遍历nums1查询。

C++核心代码：

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {stack<int> st;unordered_map<int, int> map; // 存nums2中元素的下一个更大for (int i = 0; i < nums2.size(); i++) {while (!st.empty() && nums2[i] > nums2[st.top()]) {map[nums2[st.top()]] = nums2[i];st.pop();}st.push(i);}// 处理nums1vector<int> result;for (int num : nums1) {result.push_back(map.count(num) ? map[num] : -1);}return result;
}

2. LeetCode 503: Next Greater Element II（数组循环）

问题：数组是环形的，找每个元素的下一个更大（循环查找）。
解法：把数组拉直成两倍长度，再用单调栈。例如，数组[1,2,1]变成[1,2,1,1,2,1]。

C++核心代码：

vector<int> nextGreaterElements(vector<int>& nums) {int n = nums.size();vector<int> result(n, -1);stack<int> st;// 遍历两遍数组for (int i = 0; i < 2 * n; i++) {int num = nums[i % n]; // 循环索引while (!st.empty() && num > nums[st.top()]) {result[st.top()] = num;st.pop();}if (i < n) st.push(i); // 只存第一遍的索引}return result;
}

3. LeetCode 84: Largest Rectangle in Histogram（难题，柱状图最大矩形）

问题：给定柱状图的高度数组，求最大矩形面积。
解法：用单调递增栈。遍历每个柱子，栈存索引；当当前柱子高度 < 栈顶时，弹出栈顶并计算以它为高的矩形面积。

C++核心代码：

int largestRectangleArea(vector<int>& heights) {stack<int> st;int maxArea = 0;heights.push_back(0); // 加哨兵值，处理剩余栈for (int i = 0; i < heights.size(); i++) {while (!st.empty() && heights[i] < heights[st.top()]) {int h = heights[st.top()]; // 当前高度st.pop();int width = st.empty() ? i : (i - st.top() - 1); // 计算宽度maxArea = max(maxArea, h * width);}st.push(i);}return maxArea;
}

其他应用

雨水收集问题（LeetCode 42）：用单调栈算每个位置的积水。
每日温度（LeetCode 739）：找需要等几天才有更高温度。
最大矩形（LeetCode 85）：二维矩阵中找最大矩形，结合单调栈。

接地气总结：单调栈专治“找左邻居右邻居”的病。记住口诀：单调栈，顺序排；遇大弹出，遇小入栈；一次遍历，效率贼高！

六、实例分析：柱状图最大矩形详解

我们挑LeetCode 84题（柱状图最大矩形）深入分析，因为它是单调栈的招牌应用。接地气地说，就是“在高低不平的柱子里，找出能画出的最大长方形”。

问题描述

给定一个整数数组heights，表示柱状图的高度。例如，heights = [2,1,5,6,2,3]，柱状图如下：

      ____| ||  | |__
__ |  | |  |
| || || || | 
------------2 1 5 6 2 3

求最大矩形面积（上图最大是10，来自高度5和6的柱子）。

单调栈解法思路

用单调递增栈（栈底到顶高度递增）：

遍历柱子：每个柱子尝试入栈。
维护单调性：如果当前柱子高度 < 栈顶高度，说明栈顶柱子找到了右边界（当前索引），弹出栈顶。
计算面积：弹出时，以弹出柱子的高度为矩形高，宽度是右边界减左边界（左边界是栈新顶索引）。
哨兵技巧：在数组末尾加高度0的柱子，强制弹出所有栈中元素。

分步图解（以heights = [2,1,5,6,2,3]为例）

步骤0：加哨兵，heights变成[2,1,5,6,2,3,0]。
i=0: 高度2，栈空，入栈（栈：[0]）。
i=1: 高度1 < 2（栈顶），弹出索引0：
- 高度h=2，栈空，宽度= i - 0 = 1（左边界是-1？实际用i=1），面积=2*1=2。
- 入栈1（栈：[1]）。
i=2: 高度5 > 1，入栈（栈：[1,2]）。
i=3: 高度6 > 5，入栈（栈：[1,2,3]）。
i=4: 高度2 < 6，弹出索引3：
- h=6，栈顶索引2（高度5），宽度= i - 2 - 1 = 4-2-1=1，面积=6*1=6。
- 高度2 < 5，弹出索引2：
  - h=5，栈顶索引1（高度1），宽度= i - 1 - 1 = 4-1-1=2，面积=5*2=10（最大）。
- 入栈4（栈：[1,4]）。
i=5: 高度3 > 2，入栈（栈：[1,4,5]）。
i=6: 高度0 < 3，弹出索引5：
- h=3，栈顶4（高度2），宽度=6-4-1=1，面积=3*1=3。
- 高度0 < 2，弹出索引4：
  - h=2，栈顶1（高度1），宽度=6-1-1=4，面积=2*4=8。
- 高度0 < 1，弹出索引1：
  - h=1，栈空，宽度=6，面积=1*6=6。
结束：最大面积是10。

C++完整代码

#include <iostream>
#include <vector>
#include <stack>
using namespace std;int largestRectangleArea(vector<int>& heights) {heights.push_back(0); // 加哨兵值stack<int> st;int maxArea = 0;for (int i = 0; i < heights.size(); i++) {while (!st.empty() && heights[i] < heights[st.top()]) {int h = heights[st.top()];st.pop();int left = st.empty() ? -1 : st.top(); // 左边界索引int width = i - left - 1; // 宽度计算maxArea = max(maxArea, h * width);}st.push(i);}return maxArea;
}int main() {vector<int> heights = {2,1,5,6,2,3};cout << "最大矩形面积: " << largestRectangleArea(heights) << endl; // 输出10return 0;
}

为什么高效？

时间复杂度$O(n)$：每个柱子只处理一次。
空间复杂度$O(n)$：栈最多存n个索引。
接地气提示：加哨兵（末尾0）是关键，确保所有柱子都被弹出计算。

练习：自己画图模拟过程，加深理解！

七、单调栈的优缺点：什么场合用？什么场合别用？

单调栈不是万能的，我们来客观看看它的好坏，接地气评价。

优点

高效省时：时间复杂度常是$O(n)$，比暴力法$O(n^2)$快得多。比如找下一个更大元素，暴力法要双重循环，单调栈一次遍历搞定。
代码简洁：C++实现通常20行以内，逻辑清晰。
应用广泛：特别适合“基于邻居元素”的问题，如LeetCode题、面试考点。
空间可控：空间复杂度$O(n)$，栈大小不超过数组长度。

接地气说：它像“智能导航”，帮你快速找到方向，避免绕弯路。

缺点

适用场景有限：只适合单调性问题。如果问题不涉及元素顺序（如求和、排序），就别硬套。
调试麻烦：栈操作容易出错，比如索引边界处理不当（左边界计算）。
理解门槛：初学者可能觉得抽象，需要多练习。
变体复杂：如单调队列（Monotonic Queue），进阶时更难。

使用建议

推荐用：找下一个更大/更小元素、柱状图面积、雨水问题等。
不推荐用：动态规划优化不直接相关时，或问题无单调性。
接地气口诀：邻居顺序找单调，栈来帮忙快又好；若非此类别硬套，省时省力效率高。

八、进阶话题：单调队列和其他变体

单调栈只是入门，算法世界里还有更强大的工具。比如单调队列（Monotonic Queue），它能处理滑动窗口问题。接地气解释：单调栈是“单点过滤”，单调队列是“窗口过滤”。

单调队列简介

定义：队列中元素保持单调性，常用于求滑动窗口最大值/最小值。
例子：LeetCode 239: Sliding Window Maximum。

C++实现片段：

vector<int> maxSlidingWindow(vector<int>& nums, int k) {deque<int> dq; // 双端队列存索引vector<int> result;for (int i = 0; i < nums.size(); i++) {// 移除超出窗口的元素if (!dq.empty() && dq.front() == i - k) dq.pop_front();// 维护单调递减（队头最大）while (!dq.empty() && nums[i] > nums[dq.back()]) dq.pop_back();dq.push_back(i);if (i >= k - 1) result.push_back(nums[dq.front()]);}return result;
}