vlambda博客
学习文章列表

前言

现在流行的趋势是大厂越来越喜欢考算法题。接雨水问题是一道常考题目，但是却是力扣上一道困难题。能够现场写出时间复杂度为O(n)的算法无疑是一大加分项！一起来看题吧！

题目

思路

假设height数组的长度为n，我们要找出来的答案就是从索引0到索引n-1上面每一个元素能够接到的雨水的最大值的和。因此，此题具有贪心算法的重要特征：用局部最优解求出总体最优解。

贪心算法一般是这样的模版：

总结果初始化
while 目标未完成：
  解决第i个子问题
  i加一
  第i个子问题的结果放入总结果中
返回总结果

那么，每一个位置最多能够接多高的雨水呢？我们知道一个理论叫做木桶理论，即木桶能装的水由最短的木板决定。对于一个数组，我们可以理解为一个二维的“木桶”：只有左右两边各一个木板。“木板“对应本题中的左右两边的最大的数字。每一个位置能装的最高的雨水，由左右两边的最大数字中的较小的那个值决定。每一个位置都是如此。所以，左右两个“木板”的高度由下面这个公式算出：

left_max = max(left_max, height[left])
right_max = max(right_max, height[right])

这个地方用left和right两个指针是因为我们要计算左右两个木板。

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height: return 0
        n = len(height)
        left, right = 0, n-1
        lmax = height[left]
        rmax = height[right]
        res = 0
        while left <= right:
            if lmax < rmax:
                lmax = max(lmax, height[left])
                res += lmax - height[left]
                left += 1
            else:
                rmax = max(rmax, height[right])
                res += rmax - height[right]
                right -= 1
        return res