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

代码模板解析：

1. 初始化栈并加入哨兵节点（避免空栈判断）
2. 在数组末尾追加0值（确保所有柱子被处理）
3. 维护单调递增栈，当遇到较小元素时触发面积计算
4. 宽度计算采用当前索引与栈顶前一位的差值

常见踩坑点：

• 忘记处理最后剩余的柱子（需追加0触发清算）
• 宽度计算错误（应使用i - stack[-1] - 1而非简单相减）
• 未使用哨兵节点导致边界条件复杂化

3. 子数组最值差的数学拆解

LeetCode第907题要求所有子数组的最大值最小值之差的和。暴力解法需要枚举所有子数组，复杂度O(n³)。通过单调栈可以拆解为两个独立问题：

1. 计算所有子数组的最大值之和
2. 计算所有子数组的最小值之和
3. 最终结果 = 最大值之和 - 最小值之和

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. 问题转化：识别是否属于边界扩展/最值类问题
2. 单调性选择：
   • 需要找"更小"用递增栈
   • 需要找"更大"用递减栈
3. 清算逻辑设计：
   • 确定何时弹出栈顶元素（遇到破坏单调性的元素时）
   • 设计弹出时的计算结果累积方式
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验证：

1. 空输入数组
2. 全相同元素数组
3. 严格递增/递减序列
4. 包含重复元素的随机序列

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大元素"，同样可以用单调栈配合容斥原理解决。