动态规划：接雨水问题

接雨水问题

给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0)

数据范围：数组长度 0≤ n ≤2×10^5，数组中每个值满足 0<val≤10^9 ，保证返回结果满足0≤ val ≤10^9

要求：时间复杂度 O(n)

思路
刚开始的想法是，找到每个点的左和右的最高边界，它们形成的桶应该就是当前节点能接的水量。这样想的话，需要给每个节点都要计算出它的左右最高边界。那么复杂度就会增加了，O(N^2)? 明显不是最优解。

再想，要想实现O(n)，必然只能遍历数组的里面保持常数级别操作，不能再遍历数组。如何在常数操作下就能计算接水量？ 看看高手的思想：

每个点的节水量受到左右两边较小一边的影响，值为小边高度减去自己高度。所以不妨从数组左右两边开始作为桶的边界，向中间逐步计算每个点的接水量（哪边小，计算哪边的节点）。遇到更高边界，就替换桶边界。

/**
 * max water
 * @param arr int整型一维数组 the array
 * @return long长整型
 */
function maxWater( arr ) {
    // write code here
    if (!arr || arr.length < 3) return 0
    let L = 0, R = arr.length-1, maxL = 0, maxR = 0, sum = 0
    while (L < R) {  // 直到两个边界重合停止
        // 替换桶边界
        maxL = Math.max(maxL, arr[L])
        maxR = Math.max(maxR, arr[R])
        // 结算左边或者右边的节点的接水量
        if (maxL < maxR) {
            sum += maxL - arr[L++]
        }else {
            sum += maxR - arr[R--]
        }
    }
    return sum
}
module.exports = {
    maxWater : maxWater
};

总结：
花了老长时间在想，怎么实现常数级别的操作计算接水量，总是想不明白。知道用左右指针，逐渐向中间靠拢，但是没有想到一点：

如果将数组边界开始计算，并逐渐靠拢，如果某点左边界高，右边界低，就应该计算右边的节点，而不是计算左边的节点（并且已经可以计算出右边的节点的接水量）。同样，左边界低，右边界高，就应该计算左边的节点。

这一点至关重要，左右交替进行计算，然后汇总即可。就可以实现常数级别计算了。