LeetCode刷题之42.接雨水
我不知道将去向何方，但我已在路上！ 时光匆匆，虽未曾谋面，却相遇于斯，实在是莫大的缘分，感谢您的到访 ！
题目： 给定n个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 上面是由数组 [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
代码：
class Solution:
def trap(self
, height
: List
[int]) -> int:
length
= len(height
)
if length
<= 1:
return 0
result
= 0
i
,j
= 0,length
-1
zhongjian_val
= height
.index
(max(height
))
left
,right
= height
[0],height
[length
-1]
while i
<= zhongjian_val
:
if height
[i
] <= left
:
result
+= left
- height
[i
]
if height
[i
] > left
:
left
= height
[i
]
i
+= 1
while j
>= zhongjian_val
:
if height
[j
] <= right
:
result
+= right
- height
[j
]
if height
[j
] > right
:
right
= height
[j
]
j
-= 1
return(result
)
算法说明： 先将柱子数目不足两个的情况排除，返回0；然后找到最高的一个柱子，求出对应的索引zhongjian_val，从左右两边用指针left和right进行遍历，如果当前的元素小于指针处的元素，求出两者之间的落差，累加到result上；如果当前元素大于指针处的元素，将指针移动到当前元素，继续遍历，遍历到最大元素处为止，返回最后结果。
