Interview_DS_Algo 单调栈Monotonic Stack实战指南从 Maximum Width Ramp 到区间最值问题【免费下载链接】Interview_DS_AlgoSuper Repository for Coding Interview Preperation项目地址: https://gitcode.com/GitHub_Trending/in/Interview_DS_Algo单调栈Monotonic Stack是算法面试中高频出现的一类栈数据结构其核心特征是栈内元素始终保持单调递增或单调递减。本指南以 Interview_DS_Algo 仓库中 Stack/Monotonic Stack 目录收录的两道经典题目Leetcode 962 Maximum Width Ramp 与 Leetcode 3542 Minimum Operations to Convert All Elements to Zero为骨架结合仓库内 C / Java 双语言实现源码系统讲解单调栈的构造原理、两种单调方向的选取依据、时间复杂度的证明方法以及如何将下一个更小/更大元素模板迁移到子数组计数等更复杂的问题中。读完本文你将掌握单调栈的完整解题模板并能独立推导出 O(n) 时间复杂度的解决方案。一、什么是单调栈先理解栈内元素的单调不变量单调栈本质上仍然是普通的栈后进先出区别在于它维护了一个单调不变量monotonic invariant从栈底到栈顶元素值严格或非严格递增/递减。根据方向可以分为两类类型栈底 → 栈顶典型用途单调递增栈值从小到大求左侧/右侧第一个更小元素Next Smaller ElementNSE单调递减栈值从大到小求左侧/右侧第一个更大元素Next Greater ElementNGE这种维护不变量的思想使得每个元素至多入栈一次、出栈一次从而把朴素解法 O(n²) 的暴力扫描优化为 O(n)。仓库中 Stack 目录下的 stack.png 展示了栈这一基础数据结构的入栈/出栈模型而单调栈就是在该模型上增加弹出破坏单调性元素这一规则。单调栈的应用场景非常广泛仓库内大量题目都与之相关例如直方图最大矩形 Largest_Rectangle_in_Histogram.cppLeetcode 84子数组最小值之和 Sum of Subarray Minimums.cppLeetcode 907每日温度 Daily Temperatures.cppLeetcode 739移除 K 位数字 Remove K Digits.cppLeetcode 402二、实战一Maximum Width RampLeetcode 962——单调递减栈这是 Stack/Monotonic Stack/README.md 列出的第一道题完整代码见仓库文件 Maximum Width Ramp.cpp同时提供 C 与 Java 版本题目来源为 Leetcode 962源码注释标注该题出现在 Google、Amazon 的面试中。2.1 题目含义给定一个整数数组nums定义ramp为一对下标(i, j)满足i jnums[i] nums[j]要求返回所有合法 ramp 中j - i的最大值。若不存在合法 ramp 则返回 0。2.2 暴力思路与复杂度瓶颈最朴素的做法是枚举所有(i, j)对并检查条件时间复杂度 O(n²)。当n达到 10⁵ 量级时必然超时因此需要借助单调栈。2.3 单调递减栈解法O(n)仓库中的核心实现如下C 版与 Java 版逻辑完全一致//Approach (Using monotonic stack) //T.C : O(n) //S.C : O(n) class Solution { public: int maxWidthRamp(vectorint nums) { int n nums.size(); stackint st; //stores indices of the elements for(int i 0; i n; i) { if(st.empty() || nums[st.top()] nums[i]) { st.push(i); } } int ramp 0; int j n-1; while(j 0) { while(!st.empty() nums[st.top()] nums[j]) { //st.top() i int i st.top(); ramp max(ramp, j-i); st.pop(); } j--; } return ramp; } };2.4 为什么这样做是正确且最优的第一步构造候选左端点集合单调递减。从左到右扫描只把比栈顶更小或等于的下标压入栈。这样栈内下标对应的nums值从栈底到栈顶单调递减。关键在于如果一个位置i1之后存在另一个位置i2 i1且nums[i2] nums[i1]那么i2永远不会比i1更优——因为对于任意右端点jj - i2 j - i1且i2的值更大、更容易满足nums[i2] nums[j]。因此真正值得考虑的潜在最小左端点恰好构成一条单调递减的序列这也正是把复杂度从 O(n²) 降到 O(n) 的核心。第二步从右向左匹配并动态弹出。右指针j从n-1向左移动。对于每个j只要栈顶下标i满足nums[i] nums[j]就构成一个合法 ramp更新答案后弹出。由于栈内值单调递减一旦某个栈顶元素不满足条件其下方元素值更小、下标更靠左与当前j的宽度必然更小因此每个元素至多入栈一次、出栈一次整体复杂度为 O(n)空间 O(n)栈最多存 n 个下标。2.5 手推示例以nums [6, 0, 8, 2, 1, 5]为例第一阶段压栈6下标 0入栈0 6下标 1 入栈8 0不入栈2 0不入栈1 0不入栈5 0不入栈。栈内下标为[0, 1]对应值[6, 0]单调递减。第二阶段从右往左j 5值 5栈顶i 1值 0 ≤ 5更新ramp 5 - 1 4并弹出继续检查i 0值 6 5停止。j继续左移后续组合宽度均不超过 4。最终答案为 4对应(1, 5)0 5。三、实战二Minimum Operations to Convert All Elements to ZeroLeetcode 3542——单调递增栈这是 Stack/Monotonic Stack/README.md 列出的第二道题完整代码见 Minimum Operations to Convert All Elements to Zero.cpp源码同时提供了暴力法与单调递增栈最优法两个版本C / Java。3.1 题目含义给定一个非负整数数组nums一次操作可以选定一个值x将数组中所有等于x的连续段由非x或更小值分隔全部变为 0。目标是求把整个数组变为全 0 所需的最少操作次数。3.2 暴力法O(n·u)及其缺陷源码中先给出基于unordered_set的暴力实现//Approach (Brute Force) //T.C : O(n*u), u unique elements, in worst case u n //S.C : O(u), in worst case u n class Solution { public: int minOperations(vectorint nums) { unordered_setint st(begin(nums), end(nums)); //O(n) space int n nums.size(); int ops 0; for(int target : st) { //O(U*n) if(target 0) continue; bool flow false; for(int i 0; i n; i) { if(nums[i] target) { if(!flow) { flow true; ops; } } else if(nums[i] target) { flow false; } } } return ops; } };思路是对每个不同的target值从左到右扫描每当遇到一个上升沿即一个等于target的新连续段起点就计数一次若遇到更小的值则视为该段结束。当所有元素互不相同时u n复杂度退化为 O(n²)因此需要更优解法。3.3 单调递增栈最优法O(n)//Approach (Optimal using Monotonic Increasing Stack) //T.C : O(n) //S.C : O(n) class Solution { public: int minOperations(vectorint nums) { stackint st; int ops 0; for(int i 0; i nums.size(); i) { while(!st.empty() st.top() nums[i]) { st.pop(); } if(nums[i] 0) continue; if(st.empty() || st.top() nums[i]) { st.push(nums[i]); ops; } } return ops; } };3.4 单调递增栈为何能等价于操作次数关键观察一次操作真正消灭的是一个严格递增的波峰。扫描时维护单调递增栈当新元素nums[i]小于栈顶时说明此前累积的递增值已经无法继续延伸必须作为一段独立操作处理因此弹出所有比它大的栈顶它们各自已贡献过一次操作若nums[i]等于 0则直接跳过0 不需要任何操作同时充当天然的分隔符若栈为空或栈顶小于nums[i]说明这是一个新的递增波峰将其入栈并ops。每个元素同样至多入栈、出栈一次总复杂度 O(n)空间 O(n)。相比暴力法的 O(n·u)在数据量大、去重后元素多时优势明显——源码注释也明确标注了两者在最坏情况下的复杂度差异u n时暴力为 O(n²)。四、从两个例题抽象出单调栈通用模板综合 Maximum Width Ramp.cpp单调递减与 Minimum Operations to Convert All Elements to Zero.cpp单调递增两个案例可以抽象出统一框架stackint st; // 通常存下标而非值便于计算距离 for (int i 0; i n; i) { // 1. 弹出破坏单调性的元素方向由问题决定 while (!st.empty() 破坏单调性的条件(st.top(), i)) { // 2. 在弹出时结算该元素与当前 i 构成下一个更小/更大关系 结算(st.top(), i); st.pop(); } // 3. 当前元素入栈 st.push(i); }使用时要明确回答三个问题单调方向题目要找右侧第一个更小还是右侧第一个更大前者用单调递增栈弹出更大者后者用单调递减栈弹出更小者。存值还是存下标需要计算区间宽度/距离时存下标只需比较数值时可直接存值如 Leetcode 3542。严格与不严格的取舍当数组存在重复元素、且需要为每个元素唯一确定管辖区间时一边使用严格比较、另一边使用非严格比较可避免重复计数。这一点在 Sum of Subarray Minimums.cpp 中有详细注释说明若两边都取严格小于相等的元素会重复统计同一段子数组仓库实现采用左侧严格小于arr[st.top()] arr[i]、右侧非严格小于arr[st.top()] arr[i]的互补策略来消除重复。五、模板迁移同一套路解决更多仓库题目单调栈模板的通用性极强仓库中以下题目均可在理解上述两题后直接迁移Final Prices With a Special Discount in a Shop见 Stack/Monotonic Stack/Easy/Final Prices With a Special Discount in a Shop.cpp本质是右侧第一个 当前价的元素——从左到右扫描用单调递增栈维护尚未确定折扣的下标遇到prices[i] prices[st.top()]即结算折扣暴力 O(n²) 优化为 O(n)是单调栈入门的最佳第一题。Sum of Subarray MinimumsLeetcode 907见 Stack/Sum of Subarray Minimums.cpp通过getNSLNext Smaller to Left与getNSRNext Smaller to Right为每个元素计算其作为最小值的子数组数量d1 * d2把 O(n²) 的枚举压缩到 O(n)是单调栈 贡献法的进阶练习。Largest Rectangle in HistogramLeetcode 84Stack/Largest_Rectangle_in_Histogram.cpp 同样是 NSL/NSR 思想的经典应用。Daily TemperaturesLeetcode 739、Next Greater Element IILeetcode 503Stack 目录下的这两题对应下一个更大元素方向与单调递减栈完全同构。六、学习路线与仓库使用建议入门先读 Stack/Monotonic Stack/Easy/Final Prices With a Special Discount in a Shop.cpp对比其中的暴力版与单调栈版体会弹出即结算的时机。掌握模板独立手写 Maximum Width Ramp.cpp 中的两阶段算法先构造递减候选集再从右向左匹配并尝试用笔纸走一遍 2.5 节示例。理解边界条件精读 Minimum Operations to Convert All Elements to Zero.cpp 中nums[i] 0跳过与严格递增才入栈两个细节思考若去掉它们会得到什么错误答案。进阶迁移依次挑战 Sum of Subarray Minimums.cpp、Largest_Rectangle_in_Histogram.cpp特别注意 3.4 节提到的严格 / 非严格互补处理重复元素的技巧。所有源码文件均位于仓库 Stack/Monotonic Stack 与 Stack 目录下每个文件都同时包含 C 与 Java 两种实现并带有复杂度注释与公司标签非常适合作为面试前的专题冲刺材料。掌握单调栈的维护不变量 弹出时结算思想后你可以用同一套模板解决数十道高频区间/子数组问题。【免费下载链接】Interview_DS_AlgoSuper Repository for Coding Interview Preperation项目地址: https://gitcode.com/GitHub_Trending/in/Interview_DS_Algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
