1 """ 2 Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. 3 The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image! 4 Example: 5 Input: [0,1,0,2,1,0,1,3,2,1,2,1] 6 Output: 6 7 """ 8 """ 9 每个位置上积水的高度，应该等于min（左边最高的柱子高度，右边最高的柱子高度） - 这个位置上的柱子高度。10 所以先从左往右遍历把left_max数组生成，left_max[i]代表 height[i] 及其左侧最高的柱子高度。11 同理生成right_max。12 然后再遍历一次对于每个位置计算min(left_max[i], right_max[i]) - height[i]就好了13 """14 class Solution1:15 def trap(self, height):16 max_left = [0] * len(height)17 max_right = [0] * len(height)18 res = 019 for i in range(len(height)):20 if i > 0:21 max_left[i] = max(max_left[i - 1], height[i])22 else:23 max_left[i] = height[i]24 for j in range(len(height) - 1, -1, -1):25 if j < len(height) - 1:26 max_right[j] = max(max_right[j + 1], height[j])27 else:28 max_right[j] = height[j]29 for k in range(len(height)):30 res += min(max_left[k], max_right[k]) - height[k]31 return res32 33 """34 自己的想法是创建i和j分别指向每个积水槽的两端35 积水的体积 = 集水槽的短边*底的长度-中间的每个值36 但主要卡在 i，j无法寻找37 我的想法是 height[i]>height[i-1] and height[i]>height[i+1]38 但对于[2, 0, 2]这种测试案例无法解决39 """40 class Solution2:41 def trap(self, height):42 n = len(height)43 i, j = 1, 044 res = 045 while i < n-1:46 if height[i] > height[i-1] and height[i] > height[i+1]:47 j = i+148 neg = 049 while j < n - 2:50 if not (height[j] > height[j - 1] and height[j] > height[j + 1]):51 neg += height[j]52 j += 153 else:54 break55 res += min(height[i], height[j]) * (j - i - 1) - neg56 i = j57 return res