题解 | #接雨水问题#

思路很简单,就是找到划分的方法,如果找到其中靠边区域盛水的部分,计算出盛水量,然后递归求解剩下部分盛水量求和就可以了.

边界条件

• 如果数列长度小于3,柱子比三根少,就没法盛水,返回0

首先找到左右两侧比较高的部分(假设右侧比较高):

• 这样从左边(arr[0])开始,往右数的时候一定会找到比它高的柱子,这时候计算前面盛水量+剩下部分盛水量就可以了
• 如果前i根柱子都不比它高,第i根柱子盛水: arr[0]-arr[i-1]

在这里因为对arr进行reverse操作比较花费时间,所以左侧高就直接左侧数就可以了,嫌弃麻烦的话,可以直接arr倒序,然后计算的

#
# max water
# @param arr int整型一维数组 the array
# @return long长整型
#
class Solution:
    def maxWater(self , arr ):
        # write code here
        if not arr or len(arr)<3:
            return 0
        Water=0
        if arr[-1]>=arr[0]:
            left = arr[0]
            for i in range(1,len(arr)):
                if arr[i]>left:
                    return self.maxWater(arr[i:])+Water
                Water = Water+left-arr[i]
        elif arr[-1]<arr[0]:
            right = arr[-1]
            for i in range(2,len(arr)+1):
                if arr[-i]>right:
                    return self.maxWater(arr[:-i+1])+Water
                Water = Water+right-arr[-i]
        return Water