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复杂度分析方法时间复杂度空间复杂度双指针O(n)O(1)单调栈O(n)O(n)总结本题是接雨水问题的经典解法。关键点双指针从两端向中间维护左右最大高度单调栈计算凹槽中的雨水量双指针空间更优