单调栈实战：接雨水与柱状图最大矩形问题解析-育师

1. 算法训练营实战：接雨水与柱状图最大矩形问题解析

今天想和大家分享两个经典的LeetCode算法题——42.接雨水和84.柱状图中最大的矩形。这两个问题在面试中出现频率极高，也是检验候选人栈应用能力的试金石。我在算法训练营带学员时发现，很多同学即使知道要用单调栈，实际操作时还是会遇到各种边界问题。下面我就结合自己的解题经验，详细拆解这两个问题的核心思路和实现细节。

2. 接雨水问题深度解析

2.1 问题描述与暴力解法

接雨水问题描述：给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子能接多少雨水。

最直观的暴力解法是对于每个柱子，找到它左边和右边的最高柱子，然后取两者较小值减去当前柱子的高度，就是这个柱子能接的雨水量。这种方法时间复杂度O(n²)，空间复杂度O(1)。

def trap(height): res = 0 for i in range(len(height)): max_left = max(height[:i+1]) max_right = max(height[i:]) res += min(max_left, max_right) - height[i] return res

注意：这种解法在LeetCode上会超时，但理解这个思路对后续优化很重要。

2.2 动态规划优化

我们可以预先计算每个位置的左右最大值，将时间复杂度降到O(n)，空间复杂度O(n)。

def trap(height): if not height: return 0 n = len(height) left_max = [0] * n right_max = [0] * n left_max[0] = height[0] for i in range(1, n): left_max[i] = max(left_max[i-1], height[i]) right_max[-1] = height[-1] for i in range(n-2, -1, -1): right_max[i] = max(right_max[i+1], height[i]) res = 0 for i in range(n): res += min(left_max[i], right_max[i]) - height[i] return res

2.3 单调栈解法

这是最优美的解法，时间复杂度O(n)，空间复杂度O(n)。核心思路是维护一个单调递减栈，当遇到比栈顶高的柱子时，说明可能形成凹槽可以接水。

def trap(height): stack = [] res = 0 for i in range(len(height)): while stack and height[i] > height[stack[-1]]: top = stack.pop() if not stack: break distance = i - stack[-1] - 1 bounded_height = min(height[i], height[stack[-1]]) - height[top] res += distance * bounded_height stack.append(i) return res

实操心得：单调栈解法最难理解的是计算水量的部分。记住三个关键点：1) 栈中存储的是索引；2) 弹出栈顶后栈不为空才能形成凹槽；3) 水量是水平方向计算的。

3. 柱状图中最大矩形问题详解

3.1 问题描述与暴力解法

给定n个非负整数，表示柱状图中各个柱子的高度，每个柱子宽度为1，求该柱状图中能勾勒出的最大矩形的面积。

暴力解法是对于每个柱子，向左右扩展直到遇到比它矮的柱子，计算此时的矩形面积。时间复杂度O(n²)。

def largestRectangleArea(heights): max_area = 0 n = len(heights) for i in range(n): left = i while left >= 0 and heights[left] >= heights[i]: left -= 1 right = i while right < n and heights[right] >= heights[i]: right += 1 max_area = max(max_area, (right - left - 1) * heights[i]) return max_area

3.2 单调栈优化

使用单调递增栈可以在O(n)时间内解决问题。核心思路是对于每个柱子，找到它左右第一个比它矮的柱子。

def largestRectangleArea(heights): stack = [] heights = [0] + heights + [0] res = 0 for i in range(len(heights)): while stack and heights[i] < heights[stack[-1]]: top = stack.pop() res = max(res, (i - stack[-1] - 1) * heights[top]) stack.append(i) return res

注意事项：我们在原数组前后各加了一个0，这样可以处理边界情况。前面的0保证栈不为空，后面的0保证所有柱子都会被处理。

3.3 分治法思路

虽然时间复杂度最坏是O(n²)，但平均情况下表现不错。思路是找到最矮的柱子，最大面积要么在最矮柱子左边，要么在右边，要么跨越最矮柱子。

def largestRectangleArea(heights): def helper(start, end): if start > end: return 0 min_index = start for i in range(start, end+1): if heights[i] < heights[min_index]: min_index = i return max(heights[min_index] * (end - start + 1), helper(start, min_index-1), helper(min_index+1, end)) return helper(0, len(heights)-1)

4. 两个问题的对比与关联

虽然这两个问题看起来相似，都用到了单调栈，但有以下关键区别：

接雨水问题找的是每个柱子左右的最大值，维护的是单调递减栈
最大矩形问题找的是每个柱子左右的较小值，维护的是单调递增栈
接雨水计算的是垂直方向的水量，最大矩形计算的是水平方向的面积

理解这两个问题的差异对掌握单调栈的应用场景非常重要。我在训练营中常让学员做这样的对比练习：

# 对比练习：尝试用接雨水的思路解决最大矩形问题 def wrongApproach(heights): # 这是错误的解法，仅用于对比学习 stack = [] res = 0 for i in range(len(heights)): while stack and heights[i] > heights[stack[-1]]: top = stack.pop() if not stack: break distance = i - stack[-1] - 1 bounded_height = min(heights[i], heights[stack[-1]]) res = max(res, distance * bounded_height) stack.append(i) return res

5. 常见错误与调试技巧

在训练营中，我发现学员常犯以下错误：

边界条件处理不当：特别是数组开头和结尾的情况
栈中存储内容混淆：有时存值有时存索引，导致混乱
水量或面积计算公式错误：忘记减1或搞错乘数

调试技巧：

对于接雨水问题，先在小案例上手动计算预期结果
对于最大矩形问题，画出柱状图并标出每个柱子的左右边界
使用print语句输出中间结果，特别是栈的变化过程

# 调试示例：打印单调栈的变化过程 def largestRectangleAreaWithDebug(heights): stack = [] heights = [0] + heights + [0] res = 0 for i in range(len(heights)): print(f"i={i}, height={heights[i]}, stack={stack}") while stack and heights[i] < heights[stack[-1]]: top = stack.pop() if stack: area = (i - stack[-1] - 1) * heights[top] print(f"pop {top}, area={area}") res = max(res, area) stack.append(i) return res

6. 性能优化与变种问题

在实际面试中，面试官可能会问如何进一步优化或解决变种问题：

三维接雨水问题
包含负数的柱状图最大矩形
同时求接雨水和最大矩形

对于性能优化，可以考虑：

双指针法优化空间复杂度到O(1)
并行计算预处理左右最大值
使用位运算加速比较操作

# 双指针法接雨水问题 def trap(height): if not height: return 0 left, right = 0, len(height)-1 left_max = right_max = 0 res = 0 while left < right: if height[left] < height[right]: if height[left] >= left_max: left_max = height[left] else: res += left_max - height[left] left += 1 else: if height[right] >= right_max: right_max = height[right] else: res += right_max - height[right] right -= 1 return res