问题给定 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)因为仅使用了有限的额外空间几个指针变量。