1. 单调栈从入门到实战单调栈Monotonic Stack是算法领域一种特殊的数据结构它在处理下一个更大/更小元素这类问题时展现出惊人的效率。我第一次接触这个概念是在解决LeetCode 496题下一个更大元素I时当时暴力解法超时后看到讨论区有人用5行代码就解决了问题——那便是我与单调栈的初次相遇。单调栈的核心在于维护一个栈内元素单调递增或递减的特性。以寻找下一个更大元素为例我们维护一个单调递减栈当新元素比栈顶大时不断弹出栈顶元素此时新元素就是这些被弹出元素的下一个更大元素。这种处理方式将O(n²)的时间复杂度优化到了O(n)在处理10^5量级数据时执行时间从分钟级降到了毫秒级。2. 单调栈的工作原理2.1 基础操作原理单调栈的工作流程可以通过一个具体例子理解。假设我们要为数组[3,1,4,2,5]每个元素找下一个更大元素初始化空栈结果数组初始为[-1,-1,-1,-1,-1]处理3栈空直接入栈 → 栈[3]处理113入栈 → 栈[3,1]处理441弹出1记录1的下一个更大是4 → 结果[ -1,-1,4,-1,-1] 43弹出3记录3的下一个更大是4 → 结果[4,-1,4,-1,-1] 栈空4入栈 → 栈[4]处理224入栈 → 栈[4,2]处理552弹出2记录2的下一个更大是5 → 结果[4,-1,4,5,-1] 54弹出4记录4的下一个更大是5 → 结果[4,-1,5,5,-1] 栈空5入栈 → 栈[5]结束栈中剩余元素5没有下一个更大元素保持-12.2 单调性的维护技巧在实际编码中维护单调性有以下几个关键点选择单调递增还是递减取决于问题需求。找下一个更大元素用递减栈找下一个更小元素用递增栈通常存储元素索引而非值方便计算距离等衍生问题边界处理要小心特别是栈空时的判断处理相等元素时根据题目要求决定是严格单调还是非严格单调3. C实现单调栈的四种方式3.1 基础数组实现const int MAXN 1e55; int stk[MAXN], top 0; void push(int x) { while(top 0 stk[top-1] x) { // 单调递减栈 // 处理弹出的元素 top--; } stk[top] x; }3.2 STL stack实现#include stack using namespace std; stackint monoStack; void process(int x) { while(!monoStack.empty() monoStack.top() x) { int val monoStack.top(); monoStack.pop(); // 处理val } monoStack.push(x); }3.3 泛型模板实现templatetypename T, typename Comp lessT class MonotonicStack { private: stackT data; Comp comp; public: void push(T item) { while(!data.empty() comp(data.top(), item)) { T popped data.top(); data.pop(); // 处理popped } data.push(item); } // 其他成员函数... };3.4 带索引的增强实现vectorint nextGreater(vectorint nums) { int n nums.size(); vectorint res(n, -1); stackint stk; // 存储索引 for(int i 0; i n; i) { while(!stk.empty() nums[stk.top()] nums[i]) { res[stk.top()] nums[i]; stk.pop(); } stk.push(i); } return res; }4. 单调栈的五大经典应用4.1 下一个更大元素系列LeetCode上有多个变种题下一个更大元素I基础版下一个更大元素II循环数组下一个更大元素III数字重组以503题为例循环数组的处理技巧是遍历两次数组vectorint nextGreaterElements(vectorint nums) { int n nums.size(); vectorint res(n, -1); stackint stk; for(int i 0; i 2*n; i) { int idx i % n; while(!stk.empty() nums[stk.top()] nums[idx]) { res[stk.top()] nums[idx]; stk.pop(); } if(i n) stk.push(idx); } return res; }4.2 柱状图最大矩形LeetCode 84这是单调栈的经典应用关键在于找到每根柱子左右第一个比它矮的柱子int largestRectangleArea(vectorint heights) { heights.push_back(0); // 哨兵 stackint stk; int maxArea 0; for(int i 0; i heights.size(); ) { if(stk.empty() || heights[i] heights[stk.top()]) { stk.push(i); } else { int h heights[stk.top()]; stk.pop(); int w stk.empty() ? i : i - stk.top() - 1; maxArea max(maxArea, h * w); } } return maxArea; }4.3 接雨水问题LeetCode 42单调栈解法可以看作是对每个凹槽进行计算int trap(vectorint height) { stackint stk; int res 0; for(int i 0; i height.size(); i) { while(!stk.empty() height[i] height[stk.top()]) { int bottom stk.top(); stk.pop(); if(stk.empty()) break; int left stk.top(); int h min(height[left], height[i]) - height[bottom]; res h * (i - left - 1); } stk.push(i); } return res; }4.4 每日温度LeetCode 739这是单调栈最直观的应用求需要等待的天数vectorint dailyTemperatures(vectorint T) { vectorint res(T.size(), 0); stackint stk; for(int i 0; i T.size(); i) { while(!stk.empty() T[i] T[stk.top()]) { res[stk.top()] i - stk.top(); stk.pop(); } stk.push(i); } return res; }4.5 股票跨度问题LeetCode 901维护一个单调递减栈存储价格和对应的跨度class StockSpanner { stackpairint,int stk; // price, span public: int next(int price) { int span 1; while(!stk.empty() stk.top().first price) { span stk.top().second; stk.pop(); } stk.push({price, span}); return span; } };5. 单调栈的调试技巧与常见错误5.1 常见错误类型栈空判断遗漏在弹出前必须检查!stack.empty()相等元素处理不当根据题目决定是否弹出相等元素索引与值混淆特别是在计算宽度时容易出错循环数组边界忘记处理循环情况或重复处理初始化问题结果数组初始值设置不当5.2 可视化调试方法我常用的调试方法是打印栈状态void printStack(stackint stk, vectorint nums) { cout Stack: ; while(!stk.empty()) { cout nums[stk.top()] ; stk.pop(); } cout endl; } // 在关键位置调用 printStack(stk, nums);5.3 单元测试用例设计好的测试用例应该包含空输入单元素数组全递增/递减序列有重复元素的序列已经满足条件的序列随机大数测试例如测试下一个更大元素TEST(NextGreaterTest, BasicCases) { Solution sol; EXPECT_EQ(sol.nextGreater({1}), {-1}); EXPECT_EQ(sol.nextGreater({3,2,1}), {-1,-1,-1}); EXPECT_EQ(sol.nextGreater({1,2,3}), {2,3,-1}); EXPECT_EQ(sol.nextGreater({1,3,4,2}), {3,4,-1,-1}); EXPECT_EQ(sol.nextGreater({4,3,2,5}), {5,5,5,-1}); }6. 单调栈的性能优化6.1 时间复杂度分析单调栈每个元素最多入栈一次、出栈一次因此时间复杂度是O(n)。这比暴力解法的O(n²)有质的飞跃。6.2 空间复杂度优化如果只需要单向查找如只要左边或右边的极值可以复用输入数组作为输出对于特定问题可以用位运算压缩存储信息在确定问题规模不大时使用固定大小数组替代STL stack6.3 多问题组合处理有些题目需要同时计算左右边界可以通过一次遍历完成void processBothSides(vectorint nums) { int n nums.size(); vectorint left(n, -1), right(n, -1); stackint stk; // 从左到右找右边第一个更大 for(int i 0; i n; i) { while(!stk.empty() nums[stk.top()] nums[i]) { right[stk.top()] i; stk.pop(); } stk.push(i); } // 清空栈后从右到左找左边第一个更大 stk stackint(); for(int i n-1; i 0; --i) { while(!stk.empty() nums[stk.top()] nums[i]) { left[stk.top()] i; stk.pop(); } stk.push(i); } }7. 单调栈的扩展应用7.1 二维矩阵问题LeetCode 85题最大矩形可以转化为柱状图问题int maximalRectangle(vectorvectorchar matrix) { if(matrix.empty()) return 0; int m matrix.size(), n matrix[0].size(); vectorint heights(n, 0); int maxArea 0; for(int i 0; i m; i) { for(int j 0; j n; j) { heights[j] matrix[i][j] 1 ? heights[j]1 : 0; } maxArea max(maxArea, largestRectangleArea(heights)); } return maxArea; }7.2 前K个高频元素LeetCode 347虽然这题通常用堆解决但也可以用单调栈vectorint topKFrequent(vectorint nums, int k) { unordered_mapint,int freq; for(int num : nums) freq[num]; stackpairint,int stk; for(auto [num, cnt] : freq) { while(!stk.empty() stk.top().second cnt stk.size() (freq.size() - stk.size()) k) { stk.pop(); } if(stk.size() k) stk.push({num, cnt}); } vectorint res; while(!stk.empty()) { res.push_back(stk.top().first); stk.pop(); } return res; }7.3 字符串去重LeetCode 316维护字典序最小的字符串string removeDuplicateLetters(string s) { vectorint count(26, 0); vectorbool inStack(26, false); stackchar stk; for(char c : s) count[c-a]; for(char c : s) { count[c-a]--; if(inStack[c-a]) continue; while(!stk.empty() stk.top() c count[stk.top()-a] 0) { inStack[stk.top()-a] false; stk.pop(); } stk.push(c); inStack[c-a] true; } string res; while(!stk.empty()) { res stk.top() res; stk.pop(); } return res; }8. 单调栈与其他数据结构的结合8.1 单调栈并查集解决某些区间合并问题如计算每个元素作为最小值/最大值的区间8.2 单调栈线段树处理带修改操作的区间极值查询8.3 单调栈前缀和优化某些区间统计问题如子数组和的最大/最小值8.4 单调栈动态规划典型应用是LeetCode 975题奇偶跳使用单调栈预处理每个位置的下一步9. 工业级应用案例分析9.1 内存管理中的页面替换LFU缓存算法可以用单调栈思想优化9.2 股票交易系统计算支撑位和阻力位时可以用单调栈识别关键价格点9.3 地理信息系统处理地形数据时用单调栈计算积水区域和山峰连线10. 学习资源与进阶路径10.1 推荐练习题目基础496、503、739、901进阶42、84、316、321、402挑战85、2289、2281、228210.2 可视化工具VisuAlgo的单调栈演示LeetCode动画题解自己实现一个逐步演示的网页工具10.3 参考书籍《算法导论》相关章节《编程珠玑》中的算法设计思想《挑战程序设计竞赛》中的经典例题在实际工程中我经常用单调栈优化数据处理流水线。比如最近在处理时间序列数据时用单调栈在O(n)时间内找出了所有关键转折点而原本的滑动窗口方法需要O(n²)时间。当处理百万级数据时这种优化将执行时间从小时级降到了秒级。
1. 单调栈从入门到实战单调栈Monotonic Stack是算法领域一种特殊的数据结构它在处理下一个更大/更小元素这类问题时展现出惊人的效率。我第一次接触这个概念是在解决LeetCode 496题下一个更大元素I时当时暴力解法超时后看到讨论区有人用5行代码就解决了问题——那便是我与单调栈的初次相遇。单调栈的核心在于维护一个栈内元素单调递增或递减的特性。以寻找下一个更大元素为例我们维护一个单调递减栈当新元素比栈顶大时不断弹出栈顶元素此时新元素就是这些被弹出元素的下一个更大元素。这种处理方式将O(n²)的时间复杂度优化到了O(n)在处理10^5量级数据时执行时间从分钟级降到了毫秒级。2. 单调栈的工作原理2.1 基础操作原理单调栈的工作流程可以通过一个具体例子理解。假设我们要为数组[3,1,4,2,5]每个元素找下一个更大元素初始化空栈结果数组初始为[-1,-1,-1,-1,-1]处理3栈空直接入栈 → 栈[3]处理113入栈 → 栈[3,1]处理441弹出1记录1的下一个更大是4 → 结果[ -1,-1,4,-1,-1] 43弹出3记录3的下一个更大是4 → 结果[4,-1,4,-1,-1] 栈空4入栈 → 栈[4]处理224入栈 → 栈[4,2]处理552弹出2记录2的下一个更大是5 → 结果[4,-1,4,5,-1] 54弹出4记录4的下一个更大是5 → 结果[4,-1,5,5,-1] 栈空5入栈 → 栈[5]结束栈中剩余元素5没有下一个更大元素保持-12.2 单调性的维护技巧在实际编码中维护单调性有以下几个关键点选择单调递增还是递减取决于问题需求。找下一个更大元素用递减栈找下一个更小元素用递增栈通常存储元素索引而非值方便计算距离等衍生问题边界处理要小心特别是栈空时的判断处理相等元素时根据题目要求决定是严格单调还是非严格单调3. C实现单调栈的四种方式3.1 基础数组实现const int MAXN 1e55; int stk[MAXN], top 0; void push(int x) { while(top 0 stk[top-1] x) { // 单调递减栈 // 处理弹出的元素 top--; } stk[top] x; }3.2 STL stack实现#include stack using namespace std; stackint monoStack; void process(int x) { while(!monoStack.empty() monoStack.top() x) { int val monoStack.top(); monoStack.pop(); // 处理val } monoStack.push(x); }3.3 泛型模板实现templatetypename T, typename Comp lessT class MonotonicStack { private: stackT data; Comp comp; public: void push(T item) { while(!data.empty() comp(data.top(), item)) { T popped data.top(); data.pop(); // 处理popped } data.push(item); } // 其他成员函数... };3.4 带索引的增强实现vectorint nextGreater(vectorint nums) { int n nums.size(); vectorint res(n, -1); stackint stk; // 存储索引 for(int i 0; i n; i) { while(!stk.empty() nums[stk.top()] nums[i]) { res[stk.top()] nums[i]; stk.pop(); } stk.push(i); } return res; }4. 单调栈的五大经典应用4.1 下一个更大元素系列LeetCode上有多个变种题下一个更大元素I基础版下一个更大元素II循环数组下一个更大元素III数字重组以503题为例循环数组的处理技巧是遍历两次数组vectorint nextGreaterElements(vectorint nums) { int n nums.size(); vectorint res(n, -1); stackint stk; for(int i 0; i 2*n; i) { int idx i % n; while(!stk.empty() nums[stk.top()] nums[idx]) { res[stk.top()] nums[idx]; stk.pop(); } if(i n) stk.push(idx); } return res; }4.2 柱状图最大矩形LeetCode 84这是单调栈的经典应用关键在于找到每根柱子左右第一个比它矮的柱子int largestRectangleArea(vectorint heights) { heights.push_back(0); // 哨兵 stackint stk; int maxArea 0; for(int i 0; i heights.size(); ) { if(stk.empty() || heights[i] heights[stk.top()]) { stk.push(i); } else { int h heights[stk.top()]; stk.pop(); int w stk.empty() ? i : i - stk.top() - 1; maxArea max(maxArea, h * w); } } return maxArea; }4.3 接雨水问题LeetCode 42单调栈解法可以看作是对每个凹槽进行计算int trap(vectorint height) { stackint stk; int res 0; for(int i 0; i height.size(); i) { while(!stk.empty() height[i] height[stk.top()]) { int bottom stk.top(); stk.pop(); if(stk.empty()) break; int left stk.top(); int h min(height[left], height[i]) - height[bottom]; res h * (i - left - 1); } stk.push(i); } return res; }4.4 每日温度LeetCode 739这是单调栈最直观的应用求需要等待的天数vectorint dailyTemperatures(vectorint T) { vectorint res(T.size(), 0); stackint stk; for(int i 0; i T.size(); i) { while(!stk.empty() T[i] T[stk.top()]) { res[stk.top()] i - stk.top(); stk.pop(); } stk.push(i); } return res; }4.5 股票跨度问题LeetCode 901维护一个单调递减栈存储价格和对应的跨度class StockSpanner { stackpairint,int stk; // price, span public: int next(int price) { int span 1; while(!stk.empty() stk.top().first price) { span stk.top().second; stk.pop(); } stk.push({price, span}); return span; } };5. 单调栈的调试技巧与常见错误5.1 常见错误类型栈空判断遗漏在弹出前必须检查!stack.empty()相等元素处理不当根据题目决定是否弹出相等元素索引与值混淆特别是在计算宽度时容易出错循环数组边界忘记处理循环情况或重复处理初始化问题结果数组初始值设置不当5.2 可视化调试方法我常用的调试方法是打印栈状态void printStack(stackint stk, vectorint nums) { cout Stack: ; while(!stk.empty()) { cout nums[stk.top()] ; stk.pop(); } cout endl; } // 在关键位置调用 printStack(stk, nums);5.3 单元测试用例设计好的测试用例应该包含空输入单元素数组全递增/递减序列有重复元素的序列已经满足条件的序列随机大数测试例如测试下一个更大元素TEST(NextGreaterTest, BasicCases) { Solution sol; EXPECT_EQ(sol.nextGreater({1}), {-1}); EXPECT_EQ(sol.nextGreater({3,2,1}), {-1,-1,-1}); EXPECT_EQ(sol.nextGreater({1,2,3}), {2,3,-1}); EXPECT_EQ(sol.nextGreater({1,3,4,2}), {3,4,-1,-1}); EXPECT_EQ(sol.nextGreater({4,3,2,5}), {5,5,5,-1}); }6. 单调栈的性能优化6.1 时间复杂度分析单调栈每个元素最多入栈一次、出栈一次因此时间复杂度是O(n)。这比暴力解法的O(n²)有质的飞跃。6.2 空间复杂度优化如果只需要单向查找如只要左边或右边的极值可以复用输入数组作为输出对于特定问题可以用位运算压缩存储信息在确定问题规模不大时使用固定大小数组替代STL stack6.3 多问题组合处理有些题目需要同时计算左右边界可以通过一次遍历完成void processBothSides(vectorint nums) { int n nums.size(); vectorint left(n, -1), right(n, -1); stackint stk; // 从左到右找右边第一个更大 for(int i 0; i n; i) { while(!stk.empty() nums[stk.top()] nums[i]) { right[stk.top()] i; stk.pop(); } stk.push(i); } // 清空栈后从右到左找左边第一个更大 stk stackint(); for(int i n-1; i 0; --i) { while(!stk.empty() nums[stk.top()] nums[i]) { left[stk.top()] i; stk.pop(); } stk.push(i); } }7. 单调栈的扩展应用7.1 二维矩阵问题LeetCode 85题最大矩形可以转化为柱状图问题int maximalRectangle(vectorvectorchar matrix) { if(matrix.empty()) return 0; int m matrix.size(), n matrix[0].size(); vectorint heights(n, 0); int maxArea 0; for(int i 0; i m; i) { for(int j 0; j n; j) { heights[j] matrix[i][j] 1 ? heights[j]1 : 0; } maxArea max(maxArea, largestRectangleArea(heights)); } return maxArea; }7.2 前K个高频元素LeetCode 347虽然这题通常用堆解决但也可以用单调栈vectorint topKFrequent(vectorint nums, int k) { unordered_mapint,int freq; for(int num : nums) freq[num]; stackpairint,int stk; for(auto [num, cnt] : freq) { while(!stk.empty() stk.top().second cnt stk.size() (freq.size() - stk.size()) k) { stk.pop(); } if(stk.size() k) stk.push({num, cnt}); } vectorint res; while(!stk.empty()) { res.push_back(stk.top().first); stk.pop(); } return res; }7.3 字符串去重LeetCode 316维护字典序最小的字符串string removeDuplicateLetters(string s) { vectorint count(26, 0); vectorbool inStack(26, false); stackchar stk; for(char c : s) count[c-a]; for(char c : s) { count[c-a]--; if(inStack[c-a]) continue; while(!stk.empty() stk.top() c count[stk.top()-a] 0) { inStack[stk.top()-a] false; stk.pop(); } stk.push(c); inStack[c-a] true; } string res; while(!stk.empty()) { res stk.top() res; stk.pop(); } return res; }8. 单调栈与其他数据结构的结合8.1 单调栈并查集解决某些区间合并问题如计算每个元素作为最小值/最大值的区间8.2 单调栈线段树处理带修改操作的区间极值查询8.3 单调栈前缀和优化某些区间统计问题如子数组和的最大/最小值8.4 单调栈动态规划典型应用是LeetCode 975题奇偶跳使用单调栈预处理每个位置的下一步9. 工业级应用案例分析9.1 内存管理中的页面替换LFU缓存算法可以用单调栈思想优化9.2 股票交易系统计算支撑位和阻力位时可以用单调栈识别关键价格点9.3 地理信息系统处理地形数据时用单调栈计算积水区域和山峰连线10. 学习资源与进阶路径10.1 推荐练习题目基础496、503、739、901进阶42、84、316、321、402挑战85、2289、2281、228210.2 可视化工具VisuAlgo的单调栈演示LeetCode动画题解自己实现一个逐步演示的网页工具10.3 参考书籍《算法导论》相关章节《编程珠玑》中的算法设计思想《挑战程序设计竞赛》中的经典例题在实际工程中我经常用单调栈优化数据处理流水线。比如最近在处理时间序列数据时用单调栈在O(n)时间内找出了所有关键转折点而原本的滑动窗口方法需要O(n²)时间。当处理百万级数据时这种优化将执行时间从小时级降到了秒级。
