题解 | #接雨水问题#
接雨水问题
http://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f
#
# max water
# @param arr int整型一维数组 the array
# @return long长整型
#三指针解决接雨水问题
#1.找到数组中最大值的下标
#2.left和right从最大值下标的左边开始数
#2.1 如果left<=right 没有雨水 让left=right
#2.2 如果left>right 有雨水 arr[left]-arr[right]
#2.3 right+=1
#2.4 右边同样的做法
class Solution:
def maxWater(self , arr ):
# write code here
top=arr.index(max(arr))
left=0
right=1
water=0
while right<=top:
if arr[left]<=arr[right]:
left=right
else:
water=water+arr[left]-arr[right]
right+=1
right=len(arr)-1
left=right-1
while left>=top:
if arr[left]>=arr[right]:
right=left
else:
water=water+arr[right]-arr[left]
left-=1
return water