问题
给定 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
解法
class Solution: def trap(self, height: List[int]) -> int: """ 给定一个数组 height，每个元素代表一个柱子的高度。计算淋雨后能接多少水。 :param height: List[int] 每个柱子的高度 :return: int 能接的雨水总量 """ ans = 0 # 初始化雨水总量 left, right = 0, len(height) - 1 # 左右指针分别指向数组的两端 leftMax = rightMax = 0 # 初始化左右两边的最大高度 # 使用双指针遍历数组 while left < right: # 更新左边的最大高度 leftMax = max(leftMax, height[left]) # 更新右边的最大高度 rightMax = max(rightMax, height[right]) # 根据左右两边的柱子高度决定移动哪个指针 if height[left] < height[right]: # 如果左边的柱子高度小于右边，则雨水量由左边决定 ans += leftMax - height[left] left += 1 # 移动左指针 else: # 如果右边的柱子高度小于左边，则雨水量由右边决定 ans += rightMax - height[right] right -= 1 # 移动右指针 return ans # 返回雨水总量
算法复杂度
- 时间复杂度为O(N)，其中 N 是
height的长度，因为每个元素最多被访问两次（一次在左指针移动时，一次在右指针移动时）。 - 空间复杂度为O(1)，因为仅使用了有限的额外空间（几个指针变量）。
