单调栈原理与应用：算法竞赛与面试必备技巧

1. 单调栈算法竞赛与面试中的利器第一次接触单调栈是在刷LeetCode第42题接雨水时那种醍醐灌顶的感觉至今难忘。单调栈作为一种特殊的栈结构在解决特定类型问题时展现出的简洁高效让它成为算法竞赛和面试中的常客。单调栈的核心在于维护栈内元素的单调性递增或递减这种特性使其特别适合处理下一个更大/更小元素、边界查找这类问题。与普通栈相比单调栈通过主动淘汰不符合单调性的元素将时间复杂度优化到O(n)级别这在处理大规模数据时优势尤为明显。2. 单调栈的工作原理与实现2.1 单调性维护机制单调栈的核心在于其元素排列的单调性。以单调递减栈为例当新元素准备入栈时我们会循环检查栈顶元素是否小于新元素。如果是就弹出栈顶元素直到栈顶元素大于等于新元素或栈为空为止。这个过程确保了栈内元素始终保持单调递减的顺序。def monotonic_stack(nums): stack [] for num in nums: while stack and stack[-1] num: # 维护单调递减 stack.pop() stack.append(num) return stack这种维护机制看似简单却蕴含着精妙的设计思想通过提前淘汰不可能成为解的元素避免了后续不必要的比较操作。在实际应用中我们通常会在弹出元素时记录相关信息这正是解决问题的关键所在。2.2 两种单调栈的对比单调栈主要分为单调递增栈和单调递减栈两种类型单调递增栈栈底到栈顶元素值递增适用场景寻找元素左边/右边第一个更小的元素典型题目LeetCode 84柱状图中最大矩形单调递减栈栈底到栈顶元素值递减适用场景寻找元素左边/右边第一个更大的元素典型题目LeetCode 42接雨水选择哪种单调栈取决于具体问题的需求。例如在每日温度问题中我们需要找到后面第一个更高温度因此应该使用单调递减栈。3. 单调栈的经典应用场景3.1 下一个更大元素问题LeetCode 496题下一个更大元素I是单调栈的入门级应用。题目要求为nums1中的每个元素找到其在nums2中对应位置的下一个更大元素。def nextGreaterElement(nums1, nums2): stack [] mapping {} for num in nums2: while stack and num stack[-1]: mapping[stack.pop()] num stack.append(num) return [mapping.get(num, -1) for num in nums1]这个解法巧妙地利用了单调递减栈的特性当遇到比栈顶大的元素时说明找到了栈顶元素的下一个更大元素。时间复杂度从暴力解法的O(n²)优化到了O(n)。3.2 接雨水问题LeetCode 42题接雨水是单调栈的经典应用。这个问题要求计算柱子之间的凹槽能接多少雨水。def trap(height): stack [] water 0 for i, h in enumerate(height): while stack and h height[stack[-1]]: bottom height[stack.pop()] if not stack: break left_bound height[stack[-1]] distance i - stack[-1] - 1 water (min(left_bound, h) - bottom) * distance stack.append(i) return water这个解法使用单调递减栈维护可能的左边界。每当遇到比栈顶高的柱子时就形成了一个凹槽可以计算积水量。关键在于理解栈中存储的是索引而非高度且每次计算的是水平方向的水层。4. 单调栈的进阶应用与变形4.1 柱状图中的最大矩形LeetCode 84题要求找到柱状图中最大的矩形面积。这个问题需要同时确定每个柱子的左右边界。def largestRectangleArea(heights): stack [] max_area 0 heights [0] heights [0] # 添加哨兵 for i in range(len(heights)): while stack and heights[i] heights[stack[-1]]: h heights[stack.pop()] w i - stack[-1] - 1 max_area max(max_area, h * w) stack.append(i) return max_area这个解法使用单调递增栈并在数组前后添加了高度为0的哨兵节点简化边界处理。每当遇到比栈顶小的柱子时栈顶柱子的右边界就确定了而其左边界就是栈中的前一个元素。4.2 去除K位数字使剩余最小LeetCode 402题移掉K位数字要求从数字字符串中移除k个数字使剩下的数字最小。def removeKdigits(num, k): stack [] for digit in num: while k 0 and stack and stack[-1] digit: stack.pop() k - 1 stack.append(digit) # 处理剩余的k stack stack[:-k] if k 0 else stack # 去除前导零 result .join(stack).lstrip(0) return result if result else 0这个问题可以看作是在维护一个单调递增栈。当遇到比栈顶小的数字时移除栈顶数字可以使整体数字更小。需要注意的是处理剩余的k和前导零的特殊情况。5. 单调栈的常见误区与优化技巧5.1 易犯错误盘点在实现单调栈时有几个常见陷阱需要注意边界条件处理特别是栈为空时的操作容易导致索引越界元素相等时的处理是否需要保留相等元素取决于具体问题存储内容选择有时需要存储索引而非值如接雨水问题哨兵节点的使用适当添加哨兵可以简化代码逻辑提示在解决新问题时建议先在纸上画出栈的变化过程这能帮助理解单调栈的工作原理。5.2 性能优化技巧虽然单调栈已经是O(n)时间复杂度但在实际应用中还可以进一步优化预分配空间对于已知输入规模的问题可以预分配栈空间减少操作次数合并某些操作步骤如同时计算和更新结果并行处理某些问题可以同时维护递增和递减栈空间复用对于某些问题输入数组本身可以作为栈空间例如在每日温度问题中我们可以直接修改输入数组来存储结果def dailyTemperatures(T): stack [] res [0] * len(T) for i in range(len(T)): while stack and T[i] T[stack[-1]]: prev stack.pop() res[prev] i - prev stack.append(i) return res6. 单调栈与其他数据结构的结合6.1 单调栈与动态规划有些问题需要结合单调栈和动态规划来解决。例如LeetCode 907题子数组的最小值之和需要计算所有子数组最小值的和。def sumSubarrayMins(arr): MOD 10**9 7 stack [] dp [0] * len(arr) for i in range(len(arr)): while stack and arr[stack[-1]] arr[i]: stack.pop() if stack: prev stack[-1] dp[i] dp[prev] (i - prev) * arr[i] else: dp[i] (i 1) * arr[i] stack.append(i) return sum(dp) % MOD这个解法使用单调递增栈维护最小值边界同时使用dp数组记录以每个元素结尾的子数组最小值之和。这种组合技巧在解决复杂问题时非常有效。6.2 单调栈与滑动窗口单调栈也可以与滑动窗口技巧结合使用。例如LeetCode 239题滑动窗口最大值虽然通常使用双端队列解决但也可以用单调栈的思路来处理。def maxSlidingWindow(nums, k): from collections import deque q deque() res [] for i in range(len(nums)): while q and nums[i] nums[q[-1]]: q.pop() q.append(i) if q[0] i - k: q.popleft() if i k - 1: res.append(nums[q[0]]) return res这个解法维护了一个单调递减的双端队列队首始终是当前窗口的最大值。虽然严格来说这不是栈但思想与单调栈一脉相承。7. 单调栈的实战训练建议7.1 刷题路线规划要掌握单调栈建议按照以下顺序刷题基础应用下一个更大元素 I每日温度下一个更大元素 II经典问题接雨水柱状图中最大的矩形最大矩形进阶应用移掉K位数字子数组的最小值之和去除重复字母综合应用拼接最大数132模式奇偶跳7.2 调试与验证技巧在实现单调栈算法时建议打印栈的中间状态观察其变化过程对特殊测试用例进行验证如空输入、全部相同元素使用可视化工具观察算法执行过程与暴力解法结果对比验证正确性例如可以在单调栈实现中添加调试输出def debug_monotonic_stack(nums): stack [] for i, num in enumerate(nums): print(f处理第{i}个元素{num}当前栈{stack}) while stack and nums[stack[-1]] num: popped stack.pop() print(f弹出{popped}因为{num} {nums[popped]}) stack.append(i) print(f处理后栈{stack}) return stack这种调试方法能帮助直观理解单调栈的工作机制。