LeetCode刷题必备：用单调栈5分钟搞定‘直方图最大矩形’和‘子数组最值差’-程序员充电站

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

在算法面试中，单调栈是一种极其高效的数据结构，尤其适用于解决那些看似复杂但实则模式固定的问题。本文将深入探讨如何利用单调栈快速解决LeetCode中的两个经典问题：直方图最大矩形（LeetCode 84）和子数组最值差（LeetCode 907）。通过掌握这些技巧，你可以在面试中迅速识别问题模式并给出最优解。

1. 单调栈的核心思想与应用场景

单调栈是一种特殊的栈结构，它保持栈内元素的单调性（递增或递减）。这种特性使得它在处理"下一个更大元素"或"前一个更小元素"类问题时表现出色。

单调栈的典型应用场景包括：

寻找数组中每个元素的下一个更大/更小元素
计算直方图中的最大矩形面积
求解子数组的最大值/最小值问题
处理滑动窗口极值问题

提示：单调栈的时间复杂度通常是O(n)，因为它确保每个元素只入栈和出栈一次

2. 直方图最大矩形问题（LeetCode 84）

这个问题要求我们在给定的直方图中找出面积最大的矩形。单调栈提供了一种优雅的解决方案。

2.1 解题思路拆解

初始化：创建一个空栈，并在直方图末尾添加一个高度为0的虚拟柱子
遍历柱子：
- 当当前柱子高度小于栈顶柱子高度时，开始计算面积
- 弹出栈顶元素，计算以该柱子为高的最大矩形面积
更新结果：比较并记录最大面积值

2.2 代码模板实现

def largestRectangleArea(heights): stack = [] heights = heights + [0] # 添加虚拟柱子 max_area = 0 for i, h in enumerate(heights): while stack and heights[stack[-1]] > h: height = heights[stack.pop()] width = i if not stack else i - stack[-1] - 1 max_area = max(max_area, height * width) stack.append(i) return max_area

关键点解析：

虚拟柱子的添加确保了所有柱子都会被处理
width的计算需要考虑栈为空的情况
时间复杂度：O(n)，空间复杂度：O(n)

3. 子数组最值差问题（LeetCode 907）

这个问题要求计算所有子数组的最大值与最小值之差的总和。单调栈同样能高效解决。

3.1 解题思路拆解

分解问题：总和 = 所有子数组最大值之和 - 所有子数组最小值之和
使用单调栈：
- 计算每个元素作为最大值能覆盖的区间范围
- 计算每个元素作为最小值能覆盖的区间范围
组合结果：根据覆盖范围计算贡献值并求和

3.2 代码模板实现

def sumSubarrayMins(arr): MOD = 10**9 + 7 n = len(arr) # 计算每个元素作为最小值的影响范围 left = [0] * n stack = [] for i in range(n): while stack and arr[stack[-1]] > arr[i]: stack.pop() left[i] = stack[-1] if stack else -1 stack.append(i) # 计算每个元素作为最大值的影响范围 right = [0] * n stack = [] for i in range(n-1, -1, -1): while stack and arr[stack[-1]] >= arr[i]: stack.pop() right[i] = stack[-1] if stack else n stack.append(i) # 计算最小值贡献总和 min_sum = 0 for i in range(n): min_sum += arr[i] * (i - left[i]) * (right[i] - i) # 计算最大值贡献总和（类似方法） # ... return min_sum % MOD

优化技巧：

可以一次性计算最大值和最小值的影响范围
使用数学方法直接计算贡献值而非枚举所有子数组
注意处理相等元素时的边界条件

4. 单调栈的通用解题模板

基于上述两个问题，我们可以总结出单调栈的通用解题模板：

4.1 单调递增栈模板

stack = [] for i in range(n): while stack and nums[stack[-1]] > nums[i]: # 处理弹出的元素 top = stack.pop() # 计算相关值 stack.append(i)

4.2 单调递减栈模板

stack = [] for i in range(n): while stack and nums[stack[-1]] < nums[i]: # 处理弹出的元素 top = stack.pop() # 计算相关值 stack.append(i)

应用场景对比表：

问题类型	适用栈类型	关键处理步骤
下一个更大元素	单调递减栈	弹出时记录当前元素是栈顶元素的下一个更大元素
直方图最大矩形	单调递增栈	弹出时计算以栈顶元素为高的矩形面积
子数组最值差	两者结合	分别计算作为最大值和最小值的影响范围