前言
数据结构与算法属于开发人员的内功，不管前端技术怎么变，框架怎么更新，版本怎么迭代，它终究是不变的内容。 始终记得在参加字节青训营的时候，月影老师说过的一句话，不要问前端学不学算法。计算机学科的每一位都有必要了解算法，有
写出高质量代码的潜意识。
一、问题描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
网络异常，图片无法展示
|
输入：height = [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 = [4,2,0,3,2,5] 输出：9
提示：
- n == height.length
- 1 <= n <= 2 * 104
- 0 <= height[i] <= 105
二、思路讲解
本题的实现思路是我一个好朋友想出来的，相比力扣上的其它题解，这个题的解法真的很巧妙。
如图: 最终我们需要求得的面积为 蓝色部分面积 + 红色部分面积 - 整个正方形的面积 - 黑色的部分
先看蓝色和红色部分咋求:
- 状态变量 h2 记录当前黑色柱体的最大值，从后往前迭代，面积等于 每次记录的h2的和
- 红色面积和蓝色面积类似，只不过红色面积迭代的过程是从前往后的。 黑色部分面积： 所有的height[i]之和
上代码！
三、AC代码
var trap = function(height) { // h1 负责记录从前往后迭代的最大值求蓝色面积 , h2 负责红色面积 let res = 0 , h1 = 0 , h2 = 0 for(let i = 0, j = height.length - 1;i < height.length && j >= 0 ; i++, j-- ){ h1 = Math.max(height[i], h1) h2 = Math.max(height[j], h2) res = res + h1 + h2 - height[i] // 红色面积 + 蓝色面积 - 黑色面积 } return res - height.length * h1 // 最终的面积 - 整个方形的面积 };
四、测试结果
后续
- 地址: 接雨水
好了，本篇 力扣-接雨水到这里就结束了，我是邵小白，一个在前端领域摸爬滚打的大三学生，欢迎👍评论。
