题解 | 接雨水问题

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * max water
 * @param arr int整型一维数组 the array
 * @return long长整型
 */
function maxWater(arr) {
    // write code here
    const n = arr.length
    const max = new Array(n + 1).fill(0)
    max[0] = arr[0]
    max[n - 1] = arr[n - 1]
    // 找到左边的最大值
    for (let i = 1; i < n - 1; i++) {
        max[i] = Math.max(max[i - 1], arr[i])
    }
    let res = 0
    // 找到右边的最大值
    for (let i = n - 2; i > 0; i--) {
        const left = max[i]
        max[i] = Math.max(max[i + 1], arr[i])
        // 否则，左右两边的最大值的最小值，减去当前高度，就是能接水的高度
        res += Math.min(left, max[i]) - arr[i]
    }
    return res
}
module.exports = {
    maxWater: maxWater,
};