动态规划:接雨水问题

接雨水问题

给定一个整形数组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
};

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

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

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

有问题反馈加微信:mue233 私聊送一本电子书,绝对受益良多! 微信公众号:慕意,分享创业、使用的软件和教程~
知识星球精选推荐 » 动态规划:接雨水问题