力扣-接雨水-你没看过的解法 ！ 非动态规划 ! 近100%

前言

数据结构与算法属于开发人员的内功，不管前端技术怎么变，框架怎么更新，版本怎么迭代，它终究是不变的内容。 始终记得在参加字节青训营的时候，月影老师说过的一句话，不要问前端学不学算法。计算机学科的每一位都有必要了解算法，有写出高质量代码的潜意识。

一、问题描述

给定 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  // 最终的面积 - 整个方形的面积 
};

四、测试结果

后续

• 地址: 接雨水

好了，本篇 力扣-接雨水到这里就结束了，我是邵小白，一个在前端领域摸爬滚打的大三学生，欢迎👍评论。