leetcode42 -- Trapping Rain Water (被面过)

# 小郑之家~

### 题目

42. Trapping Rain Water
Hard

3874

71

Favorite

Share
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.

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!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6



### 解法1.

“min(left_most, right_most) > height[i]”的时候，当前坐标才能够存住水，而且存水的量是”min(left_right, right_most)-height[i]”.

class Solution:
def trap(self, height: List[int]) -> int:
water = 0

for i in range(1, len(height)):
# find left_most and right_most
left_most, right_most = 0, 0
if i==0:
left_most = 0
else:
left_most = max(height[:i])  # 不包括i
if i == len(height)-1:
right_most = 0
else:
right_most = max(height[i+1:])  # 不包括i

return water


### 法二


class Solution:
def trap(self, height: List[int]) -> int:
water = 0

left_most = [0] * len(height)
right_most = [0] * len(height)

n = len(height)
for i in range(1,n):
if i ==1:
left_most[1] = height[0]
else:
left_most[i] = max(height[i-1],left_most[i-1])

for i in range(n-2,-1, -1):
if i == n-2:
right_most[n-2] = height[-1]
else:
right_most[i] = max(height[i+1], right_most[i+1])

for i in range(len(height)):

return water



### 解法三，比较漂亮

class Solution:
def trap(self, height: List[int]) -> int:
water = 0
left_most, right_most = 0, 0

left, right = 0, len(height)-1

while left<right:
if height[left] < height[right]:  # 这时候右边高了，如果要存水还要判断左边是不是也高
if left_most > height[left]:  # 太好了，这种能存水
#water += min(left_most, height[right]) - height[left]
# 和下面的等效
water += left_most-height[left]

else:
# 不能存水，更新最大
left_most = height[left]

left += 1
else:     # 说明左边可能高,那这时候判断右边
if right_most > height[right]:
water += right_most - height[right]
else:
right_most = height[right]

right -= 1

return water