【题目链接】

题解

1. 接雨水
2. 接雨水：数学解法

思路

• 韦恩图计算交集
  

代码

class Solution:
    ### 0103 记忆化遍历（48 ms，15.1 MB）
    def trap(self, height: List[int]) -> int:
        if not height: return 0

        res, n = 0, len(height)

        # 第一次遍历得到第i个数字左边最高的柱子（左边界除外）
        l_h = [0] * n
        l_h[0] = height[0]
        for i in range(1, n):
            l_h[i] = max(height[i], l_h[i - 1])

        # 第二次遍历得到第i个数字右边最高的柱子（右边界除外）
        r_h = [0] * n
        r_h[-1] = height[-1]
        for i in range(n - 2, -1, -1):
            r_h[i] = max(height[i], r_h[i + 1])

        # 第三次遍历计算每个数字上面有多少有效空间（左、右边界除外）
        for i in range(1, n - 1):
            res += min(l_h[i], r_h[i]) - height[i]

        return res

    ### 0103 双指针（44 ms，15.1 MB）
    def trap(self, height: List[int]) -> int:
        if not height: return 0

        res = 0

        # 初始化左、右指针分别为左、右边界处
        l, r = 0, len(height) - 1

        # 初始化左、右两个动态变化的最高柱子均为0
        l_h = r_h = 0

        # 左右指针不相遇时，进行循环
        while l < r:
            # 左、右柱子中的 较小值 决定了中间每一位上的有效空间（短板效应）
            if height[l] < height[r]:
                # 若当前柱子小于最高柱子，则存在有效空间，进行累加
                if height[l] < l_h: res += l_h - height[l]
                # 否则，更新最高柱子
                else: l_h = height[l]

                l += 1 # 当前柱子计算完成后，向中间移动（l加一，r减一）
            else:
                if height[r] < r_h: res += r_h - height[r]
                else: r_h = height[r]

                r -= 1

        return res

    ### 0103 使用韦恩图计算交集（48 ms，14.8 MB）
    def trap(self, height: List[int]) -> int:
        n = len(height)

        # 初始化左、右柱子最高均为0
        l_h = r_h = 0
        # 初始化左、右阶梯型面积均为0
        l_a = r_a = 0

        # 从左到右，从右到左两个方向分别计算阶梯型面积
        for i in range(n):
            if height[i] > l_h: l_h = height[i]

            if height[n - i - 1] > r_h: r_h = height[n - i - 1]

            l_a += l_h * 1
            r_a += r_h * 1

        # 有效面积 = 左阶梯面积 + 右阶梯面积 - 整个矩形面积 - 所有柱子的总面积
        return l_a + r_a - l_h * n - sum(height)