每日一题 LeetCode 42.接雨水 【双指针】

题目链接

https://leetcode-cn.com/problems/trapping-rain-water/

题目说明

题解

主要方法：双指针 + 正反遍历

解释说明：

1. 正向遍历：先确定池子左墙初始化为第一个bar，从第 2 个 bar 开始遍历右墙，同时记录中间的 bar 高度和，当右墙大于等于左墙的时候就有第一滩积水了，[左右墙距离 * 左墙高度 - 中间 bar 和] 就是这滩积水的体积，同时将右墙认定为下一个左墙，同时重新记录bar高度和。

2. 反向遍历：和正向遍历一样，先确定池子右墙初始化最后一个 bar，从后往前遍历左墙，条件限定于大于右墙，(等于的情况表示池子左右高度相同，记录一次就可以了)

代码示例：

class Solution:

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

        size = len(height)

        # 确定池子左墙，找大于等于左墙的右墙，并记录中间bar的累计和

        ans = left = block = 0

        for right in range(1, size):

            if height[right] >= height[left]:

                ans += (right - left - 1) * height[left] - block

                left, block = right, 0

            else:

                block += height[right]

        # 确定池子右墙，找大于右墙的左墙，并记录中间bar的累计和

        right, block = size - 1, 0

        for left in range(size - 2, -1, -1):

            if height[left] > height[right]:

                ans += (right - left - 1) * height[right] - block

                right,block = left, 0

            else:

                block += height[left]

        return ans