题解 | #接雨水问题#

接雨水问题

http://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f

双指针往中间移动,若lmax>rmax则hi--,否则lo++

#
# max water
# @param arr int整型一维数组 the array
# @return long长整型
#
class Solution:
    def maxWater(self , arr ):
        # write code here
        n = len(arr)
        if n <= 3:
            return 0
        lo, hi = 0, n-1
        lmax = arr[lo]
        rmax = arr[hi]
        ans = 0
        while lo <= hi:            
            lmax = max(lmax, arr[lo])            
            rmax = max(rmax, arr[hi])
            if lmax > rmax:
                ans += rmax-arr[hi]
                hi -= 1
            else:
                ans += lmax-arr[lo]
                lo += 1
        return ans
全部评论

相关推荐

强大的马里奥:不太可能,我校计算机硕士就业率99%
点赞 评论 收藏
分享
06-25 09:33
厦门大学 Java
程序员饺子:现在日常估计没啥hc了,等到八月多估计就慢慢有了。双九✌🏻不用焦虑的
投递快手等公司9个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务