Leetcode-.42接雨水

动态规划，记录i数组前后缀的最大值

class Solution:

    def trap(self, height: List[int]) -> int:

        n=len(height)

        pre_max=n*[0]

        pre_max[0]=height[0]

        for i in range(1,n):

            pre_max[i]=max(pre_max[i-1],height[i])

        suf_max=[0]*n

        suf_max[-1]=height[-1]

        for i in range (n-2,-1,-1):

            suf_max[i]=max(suf_max[i+1],height[i])

        ans=0

        for h,pre,suf in zip(height,pre_max,suf_max):

            ans+=min(pre,suf)-h
  
        return ans

• pre_max[i]：表示从最左边到当前位置 i 为止的最大柱子高度；
  
• suf_max[i]：表示从当前位置 i 到最右边的最大柱子高度；
  

对于下标 i，下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值，下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]。