题解 | #接雨水问题#

class Solution:
    def maxWater(self , arr: List[int]) -> int:
        if len(arr) <=1:
            return 0
        max_index = arr.index(max(arr))
        left = arr[:max_index+1] 
        right = list(reversed(arr[max_index:])) #通过最高的石柱，将数组分成左右两个子数组
        return self.water(left) + self.water(right)
    def water(self,arr):
        l = 0 #左指针
        r = 1 #右指针寻找大于等于l的最近指针
        res = 0
        while r<len(arr):
            if arr[l]>arr[r]:
                r+=1
            else:
                for j in range(r-l-1):
                    res = res + arr[l] - arr[l+j+1] #累计l到r所积雨水
                l = r #新的左指针从旧的右指针开始
                r = l+1 
        return res
 #因为通过最高石柱拆分左右子数组，所以数组最后一个石柱一定是最大值，最后一个r一定是len(arr)-1,所以我们不需要考虑末尾无法积水的问题