第四章：如何高效解决接雨水问题

labuladong 如何高效解决接雨水问题

42. 接雨水

我们开两个数组 l_max 和 r_max 充当备忘录

• l_max[i] 表示位置 i 左边最高的柱子高度（包括本身在内，正着遍历）， r_max[i] 表示位置 i 右边最高的柱子高度（包括本身在内，倒着遍历）。位置 i 能保存的最大的水柱高度就是 min(l_max, r_max)- height[i]
• 初始化时，首柱子左边最大为自己：l_max[0]=height[0]。尾柱子右边最大为自己：r_max[n-1]=height[n-1]
• 预先把这两个数组计算好，避免重复计算

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if not height: return 0
        #初始化
        n=len(height)
        l_max=[0]*n
        r_max=[0]*n
        l_max[0]=height[0]
        r_max[n-1]=height[n-1]

        # 计算i对应的左右最大值
        for i in range(1,n):
            l_max[i]=max(l_max[i-1],height[i])
        for i in range(n-2,-1,-1):
            r_max[i]=max(r_max[i+1],height[i])

        # 计算面积
        ans=0
        # 也可以从1开始，for i in range(1,n): 第0个位置存不住水，面积为0
        for i in range(n): 
            ans+=min(l_max[i],r_max[i])-height[i]
        return ans