leetcode42 Trapping Rain Water

努力尽今夕，少年犹可夸。这篇文章主要讲述leetcode42 Trapping Rain Water相关的知识，希望能为你提供帮助。

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: 15def trap(self, height): 16max_left = [0] * len(height) 17max_right = [0] * len(height) 18res = 0 19for i in range(len(height)): 20if i > 0: 21max_left[i] = max(max_left[i - 1], height[i]) 22else: 23max_left[i] = height[i] 24for j in range(len(height) - 1, -1, -1): 25if j < len(height) - 1: 26max_right[j] = max(max_right[j + 1], height[j]) 27else: 28max_right[j] = height[j] 29for k in range(len(height)): 30res += min(max_left[k], max_right[k]) - height[k] 31return res 32 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: 41def trap(self, height): 42n = len(height) 43i, j = 1, 0 44res = 0 45while i < n-1: 46if height[i] > height[i-1] and height[i] > height[i+1]: 47j = i+1 48neg = 0 49while j < n - 2: 50if not (height[j] > height[j - 1] and height[j] > height[j + 1]): 51neg += height[j] 52j += 1 53else: 54break 55res += min(height[i], height[j]) * (j - i - 1) - neg 56i = j 57return res

【leetcode42 Trapping Rain Water】