用双数组实现接雨水的算法
- Ⅰ、用双数组实现接雨水：
- 1、题目描述：
- 2、解题思路：
- 3、实现代码：
- Ⅱ、小结：
Ⅰ、用双数组实现接雨水：
1、题目描述：
其一、接雨水图：
其二、描述：
给定 n 个⾮负整数表示每个宽度为 1 的柱⼦的⾼度图，计算按此排列的柱⼦，下⾬之后能接多少⾬⽔；
上⾯是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的⾼度图，在这种情况下，可以接 6 个单位的⾬⽔（蓝⾊部分表示⾬⽔）；
示例:
输⼊: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
2、解题思路：
这是⼀道⾬⽔收集的问题， 思路较难， 如上图所示，让我们求下过⾬之后最多可以积攒多少的⽔;
思路：
上图中 height 数组的每一项所能接的水数，依次求和，然后相加就将是最终的输出结果；
如何才能得到 height 数组每一项所能接的水数？
答：可以计算接雨之后的水位，减去 height 数组原本的高度，就是 height 数组每一项所能接的水数；
// 根据思路得到的代码为：
for (let i = 0; i < height.length; i++) {
area += (h[i] - height[i]) * 1; // h为下⾬之后的⽔位
}
存在的问题：如何才能计算出接雨之后的水位？
答：经过逻辑思考可知，水位的高低是根据左右两侧柱⼦的最⼤值中的较⼩值来决定的，并不是某个柱子两边的值来决定的；
如上图：height[5] 的值为0，但其水位的高度是 2，这个值的计算方法是左右两侧柱⼦的最⼤值中的较⼩值来决定，左侧所有柱子的最大值
是2，右侧所有柱子的最大值是 3，因此此时水位的高度就是左右两侧柱⼦的最⼤值中的较⼩值，就为 2；
而已知水位后，再减去对应柱子的高度，就是该位置所接的水的数值;
3、实现代码：
其一、代码为：
const trap = (height) => {
let max = 0
let volume = 0
const leftMax = []
const rightMax = []
for (let i = 0; i < height.length; i++) {
leftMax[i] = max = Math.max(height[i], max)
}
// 此时的输出结果为：[0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]
// console.log(leftMax, 11223344)
max = 0
for (let i = height.length - 1; i >= 0; i--) {
rightMax[i] = max = Math.max(height[i], max)
}
// 此时的输出结果为：[3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1]
// console.log(rightMax, 55667788)
for (let i = 0; i < height.length; i++) {
volume = volume + Math.min(leftMax[i], rightMax[i]) - height[i]
}
return volume
}
// 此时的输出结果为：6(即，能接 6 个单位的雨水);
trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])
执行 trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) 函数后代码执行的过程：
第一个循环：for (let i = height.length - 1; i >= 0; i--) {}, max = 0;
max height[i] Math.max(height[i], max) max leftMax[i]
0 0 0 0 0
0 1 1 1 1
1 0 1 1 1
1 2 2 2 2
2 1 2 2 2
2 0 2 2 2
2 1 2 2 2
2 3 3 3 3
3 2 3 3 3
3 1 3 3 3
3 2 3 3 3
3 1 3 3 3
此时 leftMax 的数组为：[0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3];
第二个循环：for (let i = height.length - 1; i >= 0; i--) {}, max = 0;
max height[i] Math.max(height[i], max) max rightMax[i]
0 1 1 1 1
1 2 2 2 2
2 1 2 2 2
2 2 2 2 2
2 3 3 3 3
3 1 3 3 3
3 0 3 3 3
3 1 3 3 3
3 2 3 3 3
3 0 3 3 3
3 1 3 3 3
3 0 3 3 3
此时 rightMax 的数组为：[3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1];
第三个循环：for (let i = 0; i < height.length; i++) {}, volume = 0;
volume leftMax[i] rightMax[i] Math.min(leftMax[i], rightMax[i]) height[i] volume
0 0 3 0 - 0 0
0 1 3 1 - 1 0
0 1 3 1 - 0 1
1 2 3 2 - 2 1
1 2 3 2 - 1 1+1
1+1 2 3 2 - 0 1+1+2
1+1+2 2 3 2 - 1 1+1+2+1
1+1+2+1 3 3 3 - 3 1+1+2+1
1+1+2+1 3 2 2 - 2 1+1+2+1
1+1+2+1 3 2 2 - 1 1+1+2+1+1
1+1+2+1+1 3 2 2 - 2 1+1+2+1+1
1+1+2+1+1 3 1 1 - 1 1+1+2+1+1
此时 volume 的最终返回值为： 1+1+2+1+1 = 6;
其二、截图为：
Ⅱ、小结：
其一、哪里有不对或不合适的地方，还请大佬们多多指点和交流！
其二、若有转发或引用本文章内容，请注明本博客地址(直接点击下面 url 跳转) https://blog.csdn.net/weixin_43405300,创作不易，且行且珍惜！
其三、有兴趣的话，可以多多关注这个专栏(Vue(Vue2+Vue3)面试必备专栏)(直接点击下面 url 跳转)：https://blog.csdn.net/weixin_43405300/category_11525646.html?spm=1001.2014.3001.5482
