问题给定 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 # 初始化雨水总量 stack list() # 使用栈来存储柱子的索引 n len(height) # 获取柱子数量 for i, h in enumerate(height): # 遍历每个柱子的高度 # 当栈不为空且当前柱子高度大于栈顶柱子高度时 while stack and h height[stack[-1]]: top stack.pop() # 弹出栈顶柱子的索引 if not stack: break # 如果栈为空跳出循环 left stack[-1] # 左边柱子的索引 # 计算宽度左边索引到当前索引的距离减去1 currWidth i - left - 1 # 计算高度左边和当前柱子高度的较小值减去中间柱子高度 currHeight min(height[left], height[i]) - height[top] # 累加雨水量宽度乘以高度 ans currWidth * currHeight stack.append(i) # 将当前柱子索引压入栈中 return ans # 返回雨水总量算法复杂度时间复杂度为O(N)其中 N 是height的长度因为每个元素最多被压入和弹出栈一次。空间复杂度为O(N)因为栈最多存储所有柱子的索引。