题解 | #接雨水问题#

class Solution:
    def maxWater(self , arr: List[int]) -> int:
        # write code here
        n = len(arr)
        res = 0
        if n == 0 or n == 1: return res
        left = 0
        right = n-1
        l_max = arr[left]
        r_max = arr[right]

        res = 0
        while left < right:
            if l_max < r_max:
                left += 1
                if arr[left] <= l_max:
                    res += l_max - arr[left]
                else:
                    l_max = arr[left]
            elif l_max >= r_max:
                right -= 1
                if arr[right] <= r_max:
                    res += r_max - arr[right]
                else:
                    r_max = arr[right]
        return res

思路：假设对于位置i而言，其左侧数组[0,i-1]的最大值l_max和其右侧数组[i+1,n-1]最大值r_max。接水量dp[i]=min(l_max, r_max) - arr[i]。这里需要考虑如果dp[i]<0，dp[i] = 0。

这里就需要考虑如何更新这个l_max和r_max。既然我们需要的是l_max和r_max中比较小的一个，那设置两个指针，一开始指向0和n-1的位置，哪一个比较小就移动哪一个指针，并在移动过程中，判断当前位置和l_max或r_max的大小，从而不断计算接水量，和更新l_max和r_max的值。