https://leetcode-cn.com/explore/interview/card/bytedance/243/array-and-sorting/1047/
image.png
思路一：
每一层一层的看，比如第m层，找到最左边的大于等于m和最右边的大于等于m
然后判断中间，如果小于m，则可接1格子水
复杂度：数组中最大的数*O(n)
如果数组中最大的数很大，这个算法会崩。。。
思路二：
单独对每个位置看，他能接到水的取决于当前位置左边的最大值和右边的最大值。
比如31204，对2看，左边最大值为3，右边最大值为4，那么2这个位置能接min(3,4)-2=1格子水。
这样我们找2个数组保存下左右最大值，然后一边扫描就ok了
算法复杂度O(n)
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
arr_len = len(height)
left_max = [0]*arr_len # 从左到右的去找到当前位置的左边最大值
right_max = [0]*arr_len # 从右往左去找当前位置右边的最大值
tmp_left = 0
tmp_right = 0
for i in range(0,arr_len):
tmp_left = max(tmp_left,height[i])
left_max[i] = tmp_left
tmp_right = max(tmp_right,height[arr_len-i-1])
right_max[arr_len-i-1] = tmp_right
result = 0
for i in range(0,arr_len):
min_height = min(left_max[i],right_max[i]) #当前位置能接水取决于左右两边最小值
if height[i]<min_height:
result += min_height - height[i]
return result
