单调栈算法：原理、实现与工程应用详解

1. 单调栈算法工程师的必备武器第一次听说单调栈是在准备Google面试的时候当时刷到Leetcode 496这道下一个更大元素的题目暴力解法O(n²)的时间复杂度让我抓耳挠腮。直到看到讨论区有人用单调栈在O(n)时间内解决那种醍醐灌顶的感觉至今难忘。单调栈就像是一把瑞士军刀看似简单却能在各种看似复杂的问题中游刃有余。单调栈的核心在于维护一个栈内元素单调递增或单调递减的特性。这种数据结构特别适合处理下一个更大/更小元素、柱状图中最大矩形这类需要比较相邻元素的问题。在实际工程中我曾在处理电商价格波动分析时就用到了单调栈的思路快速找出了价格异常波动的关键时间点。2. 单调栈的核心原理与实现2.1 单调栈的两种基本形态单调栈分为单调递增栈和单调递减栈两种基本类型单调递增栈栈底到栈顶元素保持递增单调递减栈栈底到栈顶元素保持递减以Leetcode 739每日温度为例我们需要找到每一天之后更高温度出现的天数差。这个问题完美契合单调递减栈的特性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 res这段代码中我们维护一个存储下标的栈保证栈内对应温度是递减的。当遇到更高温度时就计算天数差并更新结果。2.2 时间复杂度分析单调栈最精妙的地方在于它的时间复杂度。虽然看起来有嵌套循环但每个元素最多入栈和出栈各一次所以整体时间复杂度是O(n)。这比暴力解法的O(n²)有了质的飞跃。提示在面试中能够清晰解释为什么是O(n)而不是O(n²)会大大加分。可以类比为摊还分析的概念每个元素只被处理常数次。3. 单调栈的经典应用场景3.1 下一个更大元素系列Leetcode上有多个下一个更大元素的变种题下一个更大元素 I下一个更大元素 II (循环数组)下一个更大元素 III以503题为例处理循环数组的技巧是在原数组后再拼接一次数组或者用取模运算来模拟循环def nextGreaterElements(nums): n len(nums) res [-1] * n stack [] for i in range(2 * n): while stack and nums[i % n] nums[stack[-1]]: res[stack.pop()] nums[i % n] if i n: stack.append(i) return res3.2 柱状图最大矩形问题Leetcode 84柱状图中最大的矩形是单调栈的另一个经典应用。这道题需要同时考虑左右边界def largestRectangleArea(heights): heights [0] heights [0] stack [] res 0 for i in range(len(heights)): while stack and heights[i] heights[stack[-1]]: h heights[stack.pop()] w i - stack[-1] - 1 res max(res, h * w) stack.append(i) return res这里我们在数组前后各加一个0作为哨兵简化边界条件的处理。这种技巧在很多单调栈问题中都很有用。4. 单调栈的高级应用与变形4.1 接雨水问题Leetcode 42接雨水是单调栈的一个有趣变形。我们需要计算柱子之间能接多少雨水def trap(height): stack [] res 0 for i in range(len(height)): while stack and height[i] height[stack[-1]]: bottom stack.pop() if not stack: break left stack[-1] h min(height[left], height[i]) - height[bottom] w i - left - 1 res h * w stack.append(i) return res这个解法中我们维护一个单调递减栈。当遇到更高的柱子时计算前一个柱子能接的雨水量。4.2 最大矩形问题Leetcode 85最大矩形可以看作是柱状图问题的二维扩展。我们可以将每一行转化为柱状图高度然后复用84题的解法def maximalRectangle(matrix): if not matrix: return 0 m, n len(matrix), len(matrix[0]) heights [0] * n res 0 for i in range(m): for j in range(n): heights[j] heights[j] 1 if matrix[i][j] 1 else 0 res max(res, largestRectangleArea(heights)) return res这种将二维问题降维到一维的思路非常实用也是面试中的高频考点。5. 单调栈的常见陷阱与调试技巧5.1 边界条件处理单调栈最容易出错的就是边界条件的处理。比如在84题中如果不加哨兵就需要额外处理栈为空的情况# 不加哨兵的版本 while stack and heights[i] heights[stack[-1]]: h heights[stack.pop()] # 需要额外判断栈是否为空 w i - stack[-1] - 1 if stack else i res max(res, h * w)5.2 元素相等时的处理当遇到相等元素时是弹出还是保留这取决于具体问题。在大多数情况下我们可以选择弹出或保留都可以但有些问题需要特别注意# 在每日温度问题中遇到相同温度可以保留 while stack and T[i] T[stack[-1]]: # 只有大于才弹出 # 在接雨水问题中遇到相等高度应该弹出 while stack and height[i] height[stack[-1]]: # 大于等于就弹出5.3 调试技巧当单调栈代码出现问题时可以打印中间状态来调试def dailyTemperatures(T): stack [] res [0] * len(T) for i in range(len(T)): print(fi{i}, T[i]{T[i]}, stack{stack}) while stack and T[i] T[stack[-1]]: prev stack.pop() res[prev] i - prev print(f update res[{prev}]{res[prev]}) stack.append(i) return res6. 单调栈的工程应用实例6.1 股票价格分析在实际工程中我曾用单调栈分析股票价格的支撑位和阻力位。通过维护一个单调递减栈可以快速找出价格下跌时的关键支撑位def find_support_levels(prices): stack [] supports [] for i in range(len(prices)): while stack and prices[i] prices[stack[-1]]: stack.pop() if stack: supports.append(prices[stack[-1]]) else: supports.append(None) stack.append(i) return supports6.2 日志时间窗口分析另一个应用场景是分析服务器日志中的异常峰值。使用单调栈可以高效地找出请求量突增的时间点def find_traffic_spikes(requests, window60): spikes [] stack [] for i in range(len(requests)): while stack and requests[i] 1.5 * requests[stack[-1]]: spike_time stack.pop() spikes.append((spike_time, i - spike_time)) while stack and i - stack[0] window: stack.pop(0) stack.append(i) return spikes7. 单调栈的扩展学习资源7.1 Leetcode单调栈题目清单建议按以下顺序刷题下一个更大元素 I (简单)每日温度 (中等)下一个更大元素 II (中等)柱状图中最大的矩形 (困难)接雨水 (困难)最大矩形 (困难)股票价格跨度 (中等)7.2 可视化学习工具推荐使用VisuAlgo等算法可视化工具观察单调栈的运行过程。动态演示能帮助理解元素入栈和出栈的时机。7.3 复杂度证明的数学基础想深入理解为什么单调栈是O(n)的同学可以学习摊还分析(Amortized Analysis)的概念。这在《算法导论》第17章有详细讲解。8. 面试中的单调栈问题8.1 常见考察形式面试官可能会直接出经典单调栈题目给出实际问题让你抽象出单调栈模型要求优化一个暴力解法到O(n)8.2 解题思路模板遇到新问题时可以这样思考问题是否涉及比较相邻元素是否需要维护某种单调性能否将问题转化为下一个更大/更小元素问题8.3 面试回答技巧解释思路时可以这样表述 这个问题需要找到每个元素右边第一个比它大的元素这让我想到可以用单调栈来维护一个递减序列。当遇到比栈顶大的元素时我们就找到了栈顶元素的下一个更大元素...9. 单调栈与其他数据结构的结合9.1 单调栈前缀和Leetcode 1124表现良好的最长时间段就是单调栈和前缀和的结合def longestWPI(hours): prefix [0] for h in hours: prefix.append(prefix[-1] (1 if h 8 else -1)) stack [] for i in range(len(prefix)): if not stack or prefix[i] prefix[stack[-1]]: stack.append(i) res 0 for j in range(len(prefix)-1, -1, -1): while stack and prefix[j] prefix[stack[-1]]: res max(res, j - stack.pop()) return res9.2 单调栈动态规划有些问题需要结合动态规划的思想如Leetcode 975奇偶跳def oddEvenJumps(A): n len(A) next_higher [0] * n next_lower [0] * n # 使用单调栈预处理next_higher和next_lower # ...省略实现细节... higher [False] * n lower [False] * n higher[-1] lower[-1] True res 1 for i in range(n-2, -1, -1): higher[i] lower[next_higher[i]] if next_higher[i] ! -1 else False lower[i] higher[next_lower[i]] if next_lower[i] ! -1 else False res higher[i] return res10. 从单调栈到单调队列掌握了单调栈后可以进一步学习单调队列。它们的思想一脉相承只是操作从一端扩展到了两端。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这种维护窗口内单调性的思想在解决各种滑动窗口问题时非常高效。