LeetCode 42. Trapping Rain Water 题解

LeetCode 42. Trapping Rain Water 题解

题目描述

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

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5] 输出：9

解题思路

方法一：双指针

• 每个位置能接的雨水 = min(左边最高, 右边最高) - 当前高度
• 使用双指针从两端向中间移动

方法二：单调栈

• 使用单调递减栈
• 当遇到更高的柱子时，计算可以接的雨水

代码实现

方法一：双指针

def trap(height): if not height: return 0 left, right = 0, len(height) - 1 left_max, right_max = 0, 0 water = 0 while left < right: if height[left] < height[right]: if height[left] >= left_max: left_max = height[left] else: water += left_max - height[left] left += 1 else: if height[right] >= right_max: right_max = height[right] else: water += right_max - height[right] right -= 1 return water

方法二：单调栈

def trap(height): water = 0 stack = [] # 单调递减栈 for i, h in enumerate(height): while stack and height[stack[-1]] < h: top = stack.pop() if not stack: break # 计算雨水 distance = i - stack[-1] - 1 bounded_height = min(height[stack[-1]], h) - height[top] water += distance * bounded_height stack.append(i) return water

复杂度分析

总结

本题是接雨水问题的经典解法。

关键点：

• 双指针：从两端向中间，维护左右最大高度
• 单调栈：计算凹槽中的雨水量
• 双指针空间更优