目录

之前看面试题的时候，看到了一个接雨水的问题，和小黄鸭探讨之后，感觉很乏味呢，这里和大家分享一下这个解法。起初看到 LeetCode 下面有这道题，题号 42，有趣味的能够做一下。

问题形容

给定 n 个非负整数示意每个宽度为 1 的柱子的高度图，计算彼此排列的柱子，下雨之后能接多少雨水。

示例 1：

输出：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输入：6

实例 2：

输出：height = [4,2,0,3,2,5]
输入：9

你能不能先思考一下，遇到这种问题，你要怎么做呢?

问题剖析

首先咱们能够依据给的数组，先画进去柱子的长度。

那么咱们怎么确定接的雨水的量呢? 当然是两个都高两头低的中央，来存储水，上面暗影的局部就是贮存水的地位。

那么咱们须要对右边和左边最高水位做一个统计，这边应用到了 两个辅助数组

一个用来贮存右边的最大接雨水数，一个存储左边的最大接雨水数。

抉择两个中最小的那个作为存储水的量

当然还要减去本人柱子的高度。剩下的，就是能够接的雨水了。

代码整顿

function trap(height) {if(!height.length) return 0;
    let left = []
    let right = []
    let lmax = rmax = 0
    let len = height.length
    let result = 0
    // 把左右最大出水量求进去
    for(let i = 0; i < len; i++) {lmax = Math.max(height[i], lmax)
        rmax = Math.max(height[len-i-1], rmax)
        left[i] = lmax
        right[len- i - 1] = rmax
    }
    // 算出最小的而后累加
    for(let i = 0; i < len; i++) {result += Math.min(left[i],right[i]) - height[i]
    }
    return result
};

如果想要写法上优化一下，能够第二次遍历的时候能够应用 reduce

function trap(height) {if(!height.length) return 0;
    let left = []
    let right = []
    let lmax = rmax = 0
    let len = height.length
    for(let i = 0; i < len; i++) {lmax = Math.max(height[i], lmax)
        rmax = Math.max(height[len-i-1], rmax)
        left[i] = lmax
        right[len- i - 1] = rmax
    }
    return height.reduce((prev, item, index) => {return prev + Math.min(left[index],right[index]) - item
    }, 0)
};

剖析

• 工夫复杂度 O(n)
• 空间复杂度 O(n)

其实左边数组的值的存储是能够省略的，尽管都是空间复杂度 O(n)，然而也算小小的优化点。

function trap(height) {if(!height.length) return 0;
    let left = []
    let lmax = rmax = 0
    let len = height.length
    let result = 0
    for(let i = 0; i < len; i++) {lmax = Math.max(height[i], lmax)
        left[i] = lmax
    }
    // 从后往前遍历
    for(let i = len - 1; i >= 0; i--) {rmax = Math.max(height[i], rmax)
        result += Math.min(left[i],rmax) - height[i]
    }
    return result
};