[每天一道LeetCode] 42. 接雨水

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解法

动态编程

思路：遍历每一列i，每一列可以接的水，取决于该列左右两边最大值的较小的那一个。

我们使用两个数组

left-max - 每一列左边的最大值
right-max - 每一列右边的最大值

先从左到右遍历，得到每一列左边的最大值
再从右到左遍历，得到每一列右边的最大值
最后在从左到右遍历，将当前列的高度和该列左边最大值，该列右边最大值做比较，只有在当前列的高度同时小于该列左边最大值和该列右边最大值，当前列才能接水。接的水数量 = min(该列左边最大值, 该列右边最大值) - 当前列的高度

class Solution:
    def trap(self, height: List[int]) -> int:
        l = len(height)
        left_max, right_max = [0] * l, [0] * l
        # 先从左到右遍历，得到每一列左边的最大值
        for i in range(1, l):
            left_max[i] = max(height[i - 1], left_max[i - 1])
        # 再从右到左遍历，得到每一列右边的最大值
        for i in range(l - 2, -1, -1):
            right_max[i] = max(height[i + 1], right_max[i + 1])
        ants = 0
        for i in range(l):
            if height[i] < left_max[i] and height[i] < right_max[i]:
                ants += min(left_max[i], right_max[i]) - height[i]
        return ants

时间复杂度O(n)，空间复杂度O(n)

双指针

上面的方法扫描了三次数组，而且我们发现left_max和right_max里的每个元素，我们只使用了一次。使用双指针法，同时从两个方向来遍历数组，可以在只遍历一次数组，和使用常数级的空间来完成算法。

left_max - 左边的最大值
right_max - 右边的最大值
left - 从左往右处理的当前列
right - 从右往左处理的当前列

上面的方法，我们已经知道

每一列能接的水，由当前列的左边最大值和右边最大值中的较小值决定。

当我们从左到右遍历到i列时，left_max就是left列左边的最大值，这是确定的（因为我们已经遍历了left前的列，在这个过程中，我们可以更新left_max）。但是right_max是不是left列右边的最大值？这是不确定的。

当我们从右到左遍历到right，同理，right_max就是right列右边的最大值，这是确定的。但是left_max就不一定是right列的最大值。

对于位置left而言，它左边最大值一定是left_max，右边最大值大于等于 right_max，这时候，如果left_max<right_max成立，那么它就知道自己能存多少水了。无论右边将来会不会出现更大的right_max，都不影响这个结果。所以当left_max<right_max时，我们就希望去处理left下标，反之，我们希望去处理right下标。

class Solution:
    def trap(self, height: List[int]) -> int:
        i, j = 0, len(height) - 1
        left_max, right_max = 0, 0
        ants = 0
        while left <= right:
            if left_max < right_max:
                if height[left] < left_max:
                    ants += left_max - height[left]
                else:
                    left_max = height[left]
                left += 1
            else:
                if height[right] < right_max:
                    ants += right_max - height[right]
                else:
                    right_max = height[right]
                right -= 1
        return ants