1 巧妙的思路

看到了一个巧妙的思路：

python3

python
展开代码
class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        h1 = 0
        h2 = 0
        for i in range(len(height)):
            h1 = max(h1,height[i])
            h2 = max(h2,height[-i-1])
            ans = ans + h1 + h2 -height[i]
        return  ans - len(height)*h1

2 如何理解

将循环中这句话ans = ans + h1 + h2 -height[i]分开理解，对于所有的遍历过程中的所有h1 ，当h1 小于最大值，就会减去height[i] ，这样就得到了左边的雨水+ 右边整个面积。下图的红色表示了最终的数值。

对于所有的遍历过程中的所有h2 ，当h2 小于等于最大值，就会减去height[i] ，这样就得到了右边的雨水+ 左边整个面积。下图的橘色表示了最终的数值。

将上面的2个面积加起来，会得到 所有的雨水+ len(height)*h1 。

我真是服了。

3 动态规划

动态规划没这个思路简单。不写了。