单调栈与双指针法解决接雨水问题详解

1. 接雨水问题解析

1.1 问题描述与直观理解

接雨水问题是一个经典的算法题目，给定一个非负整数数组表示的高度图，计算这个高度图能接多少雨水。想象一下，这些高度就像是一排高低不齐的墙壁，雨水会落在这些墙壁之间形成的凹陷处。

举个例子，给定高度数组 [0,1,0,2,1,0,1,3,2,1,2,1]，对应的图形如下：

■ ■ ■■ ■ ■ ■■■ ■■■■■■

可以看到，在第二个和第三个柱子之间、第五个和第七个柱子之间等位置会形成"水坑"。我们的目标就是计算这些水坑能装多少水。

1.2 单调栈解法详解

1.2.1 单调栈的基本原理

单调栈是一种特殊的栈结构，它保证栈内元素始终保持单调递增或单调递减的顺序。在解决接雨水问题时，我们使用单调递减栈（从栈底到栈顶元素递减）。

单调栈的核心作用在于：可以高效地找到数组中每个元素左右两边第一个比它大（或小）的元素。对于接雨水问题，我们需要找到每个柱子左右两边第一个比它高的柱子。

1.2.2 算法实现步骤

让我们详细分析代码实现：

class Solution: def trap(self, height: List[int]) -> int: n = len(height) stack = [] # 存储索引的单调栈 sumall = 0 # 总储水量 for i in range(n): # 当前柱子比栈顶柱子高时 while stack and height[stack[-1]] < height[i]: bottom = stack.pop() # 弹出栈顶作为底部 if not stack: # 如果栈空了，说明没有左边界 break left = stack[-1] # 新的栈顶作为左边界 width = i - left - 1 # 计算宽度 high = min(height[i], height[left]) - height[bottom] # 计算高度 sumall += width * high # 累加当前水坑的储水量 stack.append(i) # 将当前柱子索引入栈 return sumall

1.2.3 关键点解析

1. 栈中存储的是索引：这样我们可以方便地计算宽度和获取对应的高度值。

2. 横向计算水量：当遇到一个比栈顶高的柱子时，说明可能形成了一个"水坑"。我们弹出栈顶作为底部，新的栈顶作为左边界，当前柱子作为右边界。

3. 水量计算公式：

   • 宽度 = 右边界索引 - 左边界索引 - 1
   • 高度 = min(左边界高度, 右边界高度) - 底部高度
   • 水量 = 宽度 × 高度

4. 时间复杂度：O(n)，每个元素最多入栈和出栈一次。

注意事项：在实现时容易犯的错误是忘记检查栈是否为空就直接访问栈顶元素，这会导致运行时错误。代码中通过if not stack: break来避免这个问题。

1.3 双指针解法详解

1.3.1 双指针的基本思路

双指针法是另一种解决接雨水问题的高效方法。其核心思想是：对于每个柱子，它能接的雨水量取决于它左右两边最高柱子中的较小值（短板效应）。

具体来说：

• 维护左右两个指针，分别从数组两端向中间移动
• 维护左右两边的最大值left_max和right_max
• 每次移动较小max的那一侧指针
• 计算当前指针位置的储水量并累加

1.3.2 算法实现步骤

class Solution: def trap(self, height: List[int]) -> int: n = len(height) left, right = 0, n - 1 # 左右指针 left_max = right_max = 0 # 左右最大值 sumall = 0 # 总储水量 while left <= right: # 更新左右最大值 left_max = max(left_max, height[left]) right_max = max(right_max, height[right]) # 移动较小的一侧指针 if left_max < right_max: sumall += left_max - height[left] left += 1 else: sumall += right_max - height[right] right -= 1 return sumall

1.3.3 关键点解析

1. 指针移动策略：总是移动当前最大值较小的一侧的指针。这是因为储水量由短板决定，我们关心的是较小的一侧的最大值。

2. 水量计算：对于当前指针位置，它能接的雨水量等于该侧的最大值减去当前高度。因为另一侧的最大值一定不小于当前侧的最大值（否则我们会移动另一侧的指针）。

3. 时间复杂度：O(n)，只需遍历数组一次。

4. 空间复杂度：O(1)，只使用了常数个额外变量。

实操心得：双指针法相比单调栈法更直观，代码也更简洁。但在理解为什么可以这样移动指针时需要一些思考。关键是要明白我们总是可以确定较小一侧的当前柱子的储水量，因为另一侧的最大值不会小于当前侧的最大值。

2. 柱状图中最大矩形问题

2.1 问题描述

给定一个非负整数数组表示柱状图的高度，每个柱子的宽度为1，找出柱状图中最大的矩形面积。

例如，给定高度数组 [2,1,5,6,2,3]，对应的最大矩形面积为10（柱子高度为5和6的两个柱子组成的矩形）。

2.2 单调栈解法

2.2.1 算法思路

这个问题同样可以使用单调栈来解决，但与接雨水问题有所不同：

1. 我们需要找到每个柱子左右两边第一个比它矮的柱子（而不是高的）
2. 因此使用单调递增栈（从栈底到栈顶元素递增）
3. 矩形的宽度由左右边界决定，高度由当前柱子的高度决定

2.2.2 算法实现

class Solution: def largestRectangleArea(self, heights: List[int]) -> int: heights = [0] + heights + [0] # 前后补0 n = len(heights) stack = [] # 单调递增栈 max_s = 0 # 最大面积 for i in range(n): # 当前柱子比栈顶柱子矮时 while stack and heights[i] < heights[stack[-1]]: mid = stack.pop() # 弹出栈顶作为中间柱子 left = stack[-1] # 新的栈顶作为左边界 right = i # 当前索引作为右边界 width = right - left - 1 # 计算宽度 area = width * heights[mid] # 计算面积 max_s = max(max_s, area) # 更新最大面积 stack.append(i) # 将当前索引入栈 return max_s

2.2.3 关键点解析

1. 边界处理：在原数组前后各添加一个高度为0的柱子，可以简化边界条件的处理：

   • 前面的0保证第一个柱子可以被正确处理
   • 后面的0保证所有柱子都能被弹出栈计算

2. 面积计算：

   • 高度：被弹出柱子的高度
   • 宽度：右边界索引 - 左边界索引 - 1
   • 面积 = 高度 × 宽度

3. 时间复杂度：O(n)，每个元素最多入栈和出栈一次。

常见错误：忘记处理边界条件导致栈空访问或者遗漏某些柱子的计算。通过在数组前后补0可以优雅地解决这个问题。

3. 单调栈的应用总结

3.1 单调栈的两种形式

1. 单调递减栈（用于接雨水问题）：

   • 寻找每个元素左右第一个比它大的元素
   • 适合解决"找下一个更大元素"类问题

2. 单调递增栈（用于最大矩形问题）：

   • 寻找每个元素左右第一个比它小的元素
   • 适合解决"找下一个更小元素"类问题

3.2 问题转化技巧

许多看似不同的问题其实都可以转化为单调栈问题：

1. 接雨水问题：转化为找每个柱子的左右边界
2. 最大矩形问题：转化为找��个柱子的左右边界
3. 滑动窗口最大值：也可以使用单调队列（类似单调栈的思想）

3.3 性能对比

4. 常见问题与调试技巧

4.1 接雨水问题常见错误

1. 边界条件处理不当：

   • 忘记检查栈是否为空
   • 没有正确处理第一个和最后一个柱子

2. 索引与高度混淆：

   • 错误地将高度值存入栈而不是索引
   • 计算宽度时使用了高度值

3. 水量计算错误：

   • 错误地计算了高度差
   • 忽略了底部的高度

调试技巧：可以打印出栈的状态和每次计算的水量，帮助理解算法执行过程。

4.2 最大矩形问题常见错误

1. 边界处理遗漏：

   • 忘记在数组前后补0
   • 导致某些情况下的面积没有被计算

2. 宽度计算错误：

   • 错误地计算了左右边界
   • 没有减去1得到正确的宽度

3. 面积更新时机错误：

   • 在错误的时机更新最大面积
   • 遗漏了某些可能的矩形

调试技巧：可以可视化柱状图，标记出每次计算的矩形区域，帮助理解。

4.3 单调栈的通用模板

虽然不同问题的具体实现有所不同，但单调栈的基本框架是相似的：

def monotonic_stack(nums): stack = [] result = 0 # 或其他初始值 for i in range(len(nums)): while stack and nums[i] 比较 nums[stack[-1]]: # 弹出栈顶元素并处理 top = stack.pop() # 根据具体问题计算相关值 # 更新结果 stack.append(i) # 可能需要处理栈中剩余元素 return result

关键是根据具体问题：

1. 选择合适的单调性（递增或递减）
2. 定义正确的比较条件
3. 实现恰当的处理逻辑

5. 扩展思考与实际应用

5.1 单调栈的其他应用场景

1. 下一个更大元素：给定数组，为每个元素找到下一个比它大的元素
2. 每日温度：给定每日温度列表，计算需要等待多少天才能更暖和
3. 股票跨度：计算股票价格在某些天数内的跨度

5.2 算法选择的考量

在实际面试或应用中，选择哪种算法需要考虑：

1. 问题特点：是否需要找左右边界？是找更大还是更小的元素？
2. 空间限制：是否能接受O(n)的额外空间？
3. 代码复杂度：哪种方法更容易实现且不易出错？

对于接雨水问题，我个人更倾向于双指针法，因为它空间效率更高且代码更简洁。而对于最大矩形问题，单调栈是更自然的选择。

5.3 性能优化技巧

1. 提前终止：在某些情况下可以提前结束循环
2. 并行计算：对于非常大的数据，可以考虑并行处理
3. 内存优化：重用数组或使用位操作减少内存使用

在实际工程应用中，还需要考虑数据的分布特点，有时针对特定数据分布的优化可能比通用算法更有效。