42.接雨水|算法

题干在此

42接雨水.png

我的解题

这是我的第一道算法题，从这道题我发现了我思考时的“人本位”思考逻辑。

没做到很好的把题干抽象出来，而是用生活逻辑去解题，思路比较狭窄，很人类化。

我的思路是将每一个柱子进行循环，当它的右侧有不低于它的柱子时，再判断它相邻右侧的柱子是否低于它，如果低于它，便收集两者的高度差。

再去判断它右侧第二根柱子是否低于它，如果是，那么继续收集高度差，再去判断第三根柱子…如果不是那么跳出循环，开始以下一根柱子为基准进行如上循环。

同时还要记录当前柱子的高度，如果下根柱子没有它高，说明已经取过雨水了，便跳出循环，不重复收集。

当所有柱子都循环一遍时，结束循环，返回收集数组的总数，即为雨水。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
var trap = function(height) {

    let arr = []
    let m = 0
    height.forEach((v,index)=>{
        let n = 1
        if(m <= v) {
            m = 0
        }
        while(v>height[index+n] 
        && height.slice(index+1).findIndex((k)=>{return k>height[index+n]})!==-1 
        && n+index<height.length 
        && v>=m) {
            if(height.slice(index+1).findIndex((k)=>{return k>=v})!==-1) {
                arr.push(v-height[index+n])
                m = v
            } else {
                let max = 0
                max = height.slice(index+1).sort((a,b)=>{
                    return b-a
                })[0]
                arr.push(max-height[index+n])
                m = max
            }
            n = n+1
        }
    })

    return arr.reduce((a,b)=>{
        return a+b
    }, 0)

}

我的解题思路完全就是一个人肉眼观察接多少雨水的过程，其中没有什么编程思想，只是我用代码把我所想的东西写出来了而已。我把一堆堆的雨水看成了一个整体，没有有效地把它分割开。

代码验证未通过，最后倒在了一个庞大的数组用例下，没有考虑时间复杂度，超时了。

forEach * while(findIndex) * findIndex * = O(n^5) 真的裂开了。

解题思路

柱子可以一个个地分割开，其实把雨水也分成一条条来统计就好了。

统计出从左到右排序时的最高柱子和从右到左排序时的最高的柱子。

每个柱子左侧最高（包括本身）与右侧最高（包括本身）中较低的值减去柱子本身的高度，那就是该柱子可以接住的雨水。

循环一次得到所有柱子该接到的雨水量，求和即为雨水。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var trap = function(height) {
    let max = 0
    let volumn = 0
    const leftMax = []
    const rightMax = []

    for(let i = 0; i < height.length; i++) {
        leftMax[i] = max = Math.max(height[i], max)
    }

    max = 0;

    for(let i = height.length - 1; i >= 0; i--) {
        rightMax[i] = max = Math.max(height[i], max)
    }

    for(let i = 0; i < height.length; i++) {
        volumn = volumn +  Math.min(leftMax[i], rightMax[i]) - height[i]
    }

    return volumn
};

总结

没有想到雨水按照一格格地进行统计，总把一滩雨水当成一个整体，使得我的解题思路变得特别狭窄。

做题时也没有注意复杂度，没能及时发现此路不通。没有一把“尺子”在脑子里，应该从其他方向快速去验证结果，而不是代码跑起来了才发现错误。

久违了，上进心|mess

之前的博客随着旧电脑的消失消失了。

忘了开分支备份，这波真的血亏，好气。

事已至此，先吃饭吧。