题解 | #接雨水问题#
接雨水问题
http://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f
lmax是arr[0...lo]中最高柱子的高度，rmax是arr[hi...]中最高柱子的高度
#
# max water
# @param arr int整型一维数组 the array
# @return long长整型
#
class Solution:
def maxWater(self , arr ):
# write code here
n = len(arr)
lo, hi = 0, n-1
lmax, rmax = arr[0], arr[n-1]
res = 0
while lo <= hi:
lmax = max(lmax, arr[lo])
rmax = max(rmax, arr[hi])
if lmax > rmax:
res += max(0, (rmax-arr[hi]))
hi -= 1
else:
res += max(0, (lmax-arr[lo]))
lo += 1
return res
CVTE公司福利 657人发布