单调栈算法详解：原理、模板与经典应用

1. 单调栈基础概念与核心价值单调栈Monotonic Stack是一种特殊的栈结构它在算法题解中扮演着重要角色。我第一次接触这个概念是在解决柱状图中最大矩形问题时当时暴力解法的时间复杂度高达O(n²)而单调栈将复杂度优化到了O(n)。这种数据结构的特点是栈内元素始终保持单调递增或递减的顺序这种特性使得它特别适合处理下一个更大元素这类问题。单调栈的核心价值在于它能高效解决三类典型问题寻找数组中元素右侧/左侧第一个更大/更小的元素计算数组中满足特定条件的子数组数量处理与区间极值相关的优化问题在实际工程中单调栈的应用场景包括数据库查询优化中的范围查询处理编译器优化中的寄存器分配图形处理中的轮廓线提取关键理解单调栈的单调性不是目的而是手段其本质是通过维护有序性来排除不可能成为解的候选元素从而降低时间复杂度。2. 单调栈的两种基本模板2.1 单调递增栈模板def increasing_stack(nums): stack [] for num in nums: while stack and stack[-1] num: # 维护递增性 top stack.pop() # 处理弹出的元素top process(top) stack.append(num) # 处理栈中剩余元素 while stack: top stack.pop() process(top)递增栈的典型应用场景包括寻找元素左侧第一个小于它的数计算以每个元素为最小值的最大区间解决雨水收集问题中的凹陷区域识别2.2 单调递减栈模板def decreasing_stack(nums): stack [] for num in nums: while stack and stack[-1] num: # 维护递减性 top stack.pop() # 处理弹出的元素top process(top) stack.append(num) # 处理栈中剩余元素 while stack: top stack.pop() process(top)递减栈常用于寻找元素右侧第一个大于它的数计算滑动窗口最大值解决股票跨度问题实际应用时模板中的process()函数需要根据具体问题实现。例如在每日温度问题中process()会计算当前元素与被弹出元素的索引差。3. 单调栈的四种经典变体3.1 带索引的单调栈处理需要知道元素位置的问题时我们通常在栈中存储元素索引而非值def stack_with_index(nums): stack [] res [0] * len(nums) for i in range(len(nums)): while stack and nums[stack[-1]] nums[i]: idx stack.pop() res[idx] i - idx # 计算天数差 stack.append(i) return res这种变体适用于需要知道元素间距离的问题如股票跨度需要构建左右边界映射的场景处理环形数组时的双倍数组技巧3.2 前后缀结合的单调栈某些问题需要同时维护前缀和后缀信息def prefix_suffix_stack(nums): n len(nums) left [0] * n right [0] * n stack [] # 从左到右处理左边界 for i in range(n): while stack and nums[stack[-1]] nums[i]: stack.pop() left[i] stack[-1] if stack else -1 stack.append(i) stack [] # 从右到左处理右边界 for i in range(n-1, -1, -1): while stack and nums[stack[-1]] nums[i]: stack.pop() right[i] stack[-1] if stack else n stack.append(i) return left, right这种模式在解决最大矩形面积问题时特别有效。3.3 二维单调栈处理对于矩阵类问题可以先将二维问题降维def maximalRectangle(matrix): if not matrix: return 0 m, n len(matrix), len(matrix[0]) height [0] * n max_area 0 for i in range(m): for j in range(n): height[j] height[j] 1 if matrix[i][j] 1 else 0 max_area max(max_area, largestRectangleArea(height)) return max_area def largestRectangleArea(heights): stack [-1] max_area 0 for i in range(len(heights)): while stack[-1] ! -1 and heights[stack[-1]] heights[i]: max_area max(max_area, heights[stack.pop()] * (i - stack[-1] - 1)) stack.append(i) while stack[-1] ! -1: max_area max(max_area, heights[stack.pop()] * (len(heights) - stack[-1] - 1)) return max_area3.4 带辅助数据的单调栈有时需要在栈中存储额外信息def stock_spanner(): self.stack [] # (price, span) def next(self, price): span 1 while self.stack and self.stack[-1][0] price: span self.stack.pop()[1] self.stack.append((price, span)) return span这种结构在需要累计统计值时非常有用。4. 单调栈的典型问题解析4.1 下一个更大元素问题LeetCode 496题是这类问题的典型代表def nextGreaterElement(nums1, nums2): stack [] mapping {} for num in nums2: while stack and stack[-1] num: mapping[stack.pop()] num stack.append(num) return [mapping.get(num, -1) for num in nums1]关键点使用递减栈维护待处理元素当遇到更大元素时建立映射关系未处理的元素在栈中保持有序4.2 柱状图中最大矩形LeetCode 84题的单调栈解法def largestRectangleArea(heights): stack [-1] max_area 0 heights.append(0) # 哨兵值 for i in range(len(heights)): while stack[-1] ! -1 and heights[stack[-1]] heights[i]: h heights[stack.pop()] w i - stack[-1] - 1 max_area max(max_area, h * w) stack.append(i) return max_area优化技巧添加哨兵值避免特殊处理栈内剩余元素宽度计算基于当前索引和栈顶前一个元素弹出时立即计算可能的矩形面积4.3 接雨水问题LeetCode 42题的单调栈解法def trap(height): stack [] water 0 for i in range(len(height)): while stack and height[i] height[stack[-1]]: bottom height[stack.pop()] if not stack: break left_bound height[stack[-1]] right_bound height[i] water (min(left_bound, right_bound) - bottom) * (i - stack[-1] - 1) stack.append(i) return water理解要点使用递减栈维护可能的左边界当遇到更高右边界时计算积水积水宽度由左右边界索引差决定积水高度受左右边界中的较小值限制5. 单调栈的优化技巧与常见错误5.1 性能优化技巧哨兵技巧在数组首尾添加极值避免边界检查heights [0] heights [0] # 处理原始数组提前终止当问题有特殊性质时可提前退出循环if max_possible current_max: break并行处理某些问题可以同时处理多个栈inc_stack [] dec_stack []空间复用重复利用输入数组作为输出nums[:] [mapping.get(x,x) for x in nums]5.2 常见错误与调试方法方向混淆搞错递增/递减栈的选择检查问题要求的是更大还是更小元素确认处理顺序是从左到右还是相反索引处理错误特别是在环形数组问题中打印栈内和当前处理位置辅助调试使用小规模测试用例验证边界条件遗漏空栈或数组末尾的处理添加打印语句检查边界情况考虑使用哨兵值简化逻辑复杂度误判看似O(n²)实为O(n)每个元素最多入栈出栈各一次内层while循环的总次数不超过2n调试建议在纸上手动模拟小规模案例n5左右的栈变化过程这是理解单调栈行为最有效的方法。6. 单调栈的工程实践应用6.1 数据库查询优化在数据库执行计划优化中单调栈可用于范围查询的索引合并多条件查询的最优路径选择连接操作的顺序优化示例伪代码def optimize_query(conditions): stack [] for cond in sorted(conditions, keylambda x: x.selectivity): while stack and stack[-1].cost cond.cost: stack.pop() stack.append(cond) return generate_plan(stack)6.2 编译器优化在寄存器分配场景def allocate_registers(live_ranges): stack [] for start, end in sorted(live_ranges, keylambda x: x[0]): while stack and stack[-1][1] start: free_register(stack.pop()[2]) reg get_free_register() stack.append((start, end, reg)) return stack6.3 实时数据处理处理时间序列数据时def process_stream(data_stream, window_size): stack [] results [] for timestamp, value in data_stream: while stack and timestamp - stack[0][0] window_size: stack.pop(0) # 维护时间窗口 while stack and stack[-1][1] value: stack.pop() # 维护单调性 stack.append((timestamp, value)) results.append(stack[0][1]) # 当前窗口最大值 return results7. 进阶挑战与扩展思考7.1 环形数组处理技巧对于环形问题如503.下一个更大元素IIdef nextGreaterElements(nums): n len(nums) res [-1] * n stack [] for i in range(2 * n): while stack and nums[stack[-1] % n] nums[i % n]: res[stack.pop() % n] nums[i % n] if i n: stack.append(i) return res关键点模拟环形通过遍历两倍长度数组使用取模运算处理索引只在第一圈将索引入栈7.2 多维单调栈处理二维矩阵问题时将每一行视为基座累计高度对每列应用单调栈算法逐步扩展矩阵维度7.3 与其他数据结构的结合与线段树结合解决动态区间问题class SegmentTree: # 线段树实现省略 def dynamic_range_query(nums, queries): st SegmentTree(nums) stack [] res [] for query in queries: if query.type push: while stack and stack[-1] query.val: st.update(stack.pop()) stack.append(query.val) else: res.append(st.query(query.l, query.r)) return res7.4 单调栈的数学本质从数学角度看单调栈实际上是在维护一个凸包。对于函数f(x)我们维护的栈构成了f(x)的下凸包或上凸包。这种视角可以帮助理解为什么单调栈能高效解决极值问题递增栈维护下凸包适合最小值问题递减栈维护上凸包适合最大值问题弹出操作相当于排除非极值候选点这种理解方式在解决更复杂的优化问题时特别有用比如动态规划中的斜率优化。