目录

之前看面试题的时候，看到了一个接雨水的问题，和小黄鸭探讨之后，感觉很乏味呢，这里和大家分享一下这个解法。起初看到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};