接雨水是一个经典问题，说，有一堆柱子下雨之后，那些凹下的部分会盛满水。给出每根柱子的高度和宽度，统计这组柱子能够盛多少水。
方便计算，假设每个柱子的宽度一样，柱子的高度都是整数单位。
下面这个例子，统计雨水量就是6个单位

image.png

这种问题，首先我们要知道怎么暴力统计

每根柱子上面最终能存放多少水，和几个量有关

• 柱子本身自己的高度
• 柱子左边最高的柱子高度
• 柱子右边最高的柱子高度

不是每种情况柱子上方都能存水，只有当两边的最高柱子中较矮的那个，比柱子本身还高，那么，这根柱子上方才可能盛水

用数学表示就是

时可以盛水
于是总的注水量就是

按照这个公式可以弄出一个算法，但是它的效率是 , 因为计算 不得不遍历一段子数组

def trap(self, height: List[int]) -> int:
        n = len(height)
        if n == 0:
            return 0
        
        water = 0
        for i in range(1, n - 1):
            left_max = max(height[0: i])
            right_max = max(height[i + 1:]) # 隐藏了一个for 循环
            h = min(left_max, right_max)
            if h > height[i]:
                water += (h - height[i])
        
        return water

计算每根柱子的左侧最高柱子高度，这里看起来有很多重复量。
比如 i = 5 （下标从0开始），左边最高是2，对于i = 6，, 已经计算过，可以直接利用

这样的话我们就可以用一个新的表把每个下标对应 标出来，对于 同理
这时候计算 式时， 可以在 O(1) 的时间内索引出来，整个算法的复杂度降到了 O(n)

这种方法即所谓的动态规划。

动态规划体现在，上面的 计算中，每根柱子的量 和上一根柱子的改量有关，有最优子结构，可以证明一般的关系

def trap(self, height: List[int]) -> int:
        n = len(height)
        if n <= 1:
            return 0
        
        water = 0

        l_max_h = [0] * n
        r_max_h = [0] * n
        left_max, right_max = 0, 0
        
        for i in range(1, n - 1):
             left_max = max(height[i - 1], left_max)
             right_max = max(height[n - i], right_max)
             
             l_max_h[i] = left_max
             r_max_h[n - i - 1] = right_max

        for i in range(1, n - 1):
            minh = min(l_max_h[i], r_max_h[i])
            if  minh > height[i]:
                water += (minh - height[i])
        return water

还有一种双指针的算法，可以省去索引表，只维护一个左右最大的量，然后直接一遍统计。更节省空间和时间。
可以看成是动态规划版本的优化变种算法——把维护表简化了，只维护一个左最大量和右最大量。

int trap(vector<int>& height) {
        int n = height.size();
        int left = 0, right = n - 1;

        int left_max = 0, right_max = 0;
        int water = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] > left_max) {
                    left_max = height[left];
                } else {
                    water += (left_max - height[left]);
                }
                left++;
            } else {
                if (height[right] > right_max) {
                    right_max = height[right];
                } else {
                    water += (right_max - height[right]);
                }
                right--;
            }
        }
        return water;
    }