LeetCode刷题必备：用单调栈5分钟搞定‘直方图最大矩形’和‘子数组最值差’两道经典题

LeetCode刷题必备单调栈速解两道经典难题的实战套路面试官在白板上写下直方图最大矩形和子数组最值差两道题时前排候选人已经开始冒汗——这类问题在LeetCode中属于中等偏上难度常规解法要么时间复杂度太高要么边界条件处理复杂。但如果你掌握单调栈这个数据结构中的特种部队5分钟内写出最优解并非天方夜谭。本文将拆解两道经典例题提炼出可复用的解题模板让你在面试中遇到类似问题时能快速识别模式、套用框架。1. 单调栈的核心武器库单调栈Monotonic Stack本质上是在栈的FILO特性基础上额外维护栈内元素的单调性递增或递减。这种结构特别适合解决**下一个更大/更小元素**、边界扩展类问题。其核心优势在于能将O(n²)的暴力解法优化到O(n)时间复杂度。关键操作特征单调递增栈栈底到栈顶元素值严格递增用于寻找第一个更小元素单调递减栈栈底到栈顶元素值严格递减用于寻找第一个更大元素实战技巧遇到数组中的区间最值问题时先画图模拟单调栈处理过程比直接写代码更易理解2. 直方图最大矩形的降维打击LeetCode第84题要求找到直方图中面积最大的矩形。常规思路需要双重循环计算每个柱子作为高度的最大宽度时间复杂度O(n²)。而单调栈解法只需一次遍历def largestRectangleArea(heights): stack [-1] # 哨兵节点 heights.append(0) # 触发最终清算 max_area 0 for i in range(len(heights)): while 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值确保所有柱子被处理维护单调递增栈当遇到较小元素时触发面积计算宽度计算采用当前索引与栈顶前一位的差值常见踩坑点忘记处理最后剩余的柱子需追加0触发清算宽度计算错误应使用i - stack[-1] - 1而非简单相减未使用哨兵节点导致边界条件复杂化3. 子数组最值差的数学拆解LeetCode第907题要求所有子数组的最大值最小值之差的和。暴力解法需要枚举所有子数组复杂度O(n³)。通过单调栈可以拆解为两个独立问题计算所有子数组的最大值之和计算所有子数组的最小值之和最终结果 最大值之和 - 最小值之和def sumSubarrayRanges(nums): def calculate(func): stack [] res 0 for i in range(len(nums) 1): while stack and (i len(nums) or func(nums[i], nums[stack[-1]])): mid stack.pop() left stack[-1] if stack else -1 res nums[mid] * (mid - left) * (i - mid) stack.append(i) return res return calculate(lambda x, y: x y) - calculate(lambda x, y: x y)模式识别要点使用高阶函数复用单调栈逻辑仅比较逻辑不同贡献度计算(当前元素作为最值的左边界跨度) × (右边界跨度)数组末尾虚拟节点确保清算所有元素对比两种场景的单调栈应用差异特征直方图最大矩形子数组最值差栈类型单调递增栈最大值用递减栈最小值用递增栈触发计算时机遇到更小元素时遇到破坏单调性元素时结果贡献计算方式高度 × 扩展宽度值 × 子数组组合数边界处理追加零高度柱子追加虚拟终止节点4. 单调栈的通用解题框架通过上述案例可以提炼出单调栈的四步解题法问题转化识别是否属于边界扩展/最值类问题单调性选择需要找更小用递增栈需要找更大用递减栈清算逻辑设计确定何时弹出栈顶元素遇到破坏单调性的元素时设计弹出时的计算结果累积方式边界处理初始哨兵节点通常为-1终止触发机制追加特殊值或虚拟节点将这个框架应用到其他相似题目每日温度LeetCode 739找下一个更高温度的天数 → 单调递减栈滑动窗口最大值LeetCode 239维护窗口内的递减序列 → 双端队列实现接雨水LeetCode 42找左右边界的最小值 → 左右指针或单调栈5. 面试实战中的高频失误与应对在压力环境下即使知道算法原理也容易翻车。以下是面试官反馈的常见问题及解决方案内存溢出忘记弹出栈元素导致栈无限增长修复确保每次入栈前正确处理破坏单调性的元素# 错误示范 while stack and nums[i] nums[stack[-1]]: res nums[stack[-1]] # 忘记pop会导致死循环 # 正确写法 while stack and nums[i] nums[stack[-1]]: idx stack.pop() res nums[idx]边界条件错误空栈访问stack[-1]引发异常修复初始放入哨兵值如-1时间复杂度误判误以为嵌套循环就是O(n²)实际分析每个元素最多入栈出栈各一次 → O(n)最近在帮学员mock interview时发现80%的错误都集中在边界处理。建议在写完代码后立即用以下case验证空输入数组全相同元素数组严格递增/递减序列包含重复元素的随机序列6. 单调栈的进阶应用场景掌握基础模式后可以处理更复杂的变种问题二维矩阵中的最大矩形LeetCode 85将矩阵按行转化为多个直方图问题每行高度累积前一行的非零值def maximalRectangle(matrix): if not matrix: return 0 m, n len(matrix), len(matrix[0]) height [0] * n max_area 0 for row in matrix: for j in range(n): height[j] height[j] 1 if row[j] 1 else 0 max_area max(max_area, largestRectangleArea(height)) return max_area带限制条件的最值差如子数组长度不超过k的最大值最小值差结合单调队列滑动窗口最值与单调栈思想在最近参与的代码竞赛中遇到一道变形题需要计算所有子数组的中位数之和。通过将问题转化为对于每个元素统计其作为多少个子数组的第k大元素同样可以用单调栈配合容斥原理解决。