LeetCode接雨水

题目描述

给定 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

解题思路

1、首先题目的要求是求解出所有排列的柱子，下雨之后能接多少雨水，我们可以先求解出每一列上所能接雨水的面积

2、那么如何求解当前位置（每一列）上的面积呢？

因为宽度为1，所以每一列上的面积=Math.min(left_max[i],right_max[i])-height[i];

开两个数组先记录下当前位置上左右两边高度的最大值，通过遍历不断更新最大值来记录

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
  let n=height.length;
  if(n===0) return 0;
  let res=0;

  let left_max=[] ,right_max=[];
  //记录左边数组的最大值
  left_max[0]=height[0];
  for(let i=1;i<n;i++){
    left_max[i]=Math.max(left_max[i-1],height[i]);
  }
  //记录右边数组的最大值
  right_max[n-1]=height[n-1];
  for(let i=n-2;i>=0;i--){
    right_max[i]=Math.max(right_max[i+1],height[i]);
  }
  //统计每一列的面积之和
  for(let i=0;i<n;i++){
    res+=Math.min(left_max[i],right_max[i])-height[i];
  }
  return res;
};

代码分析：

这段代码定义了一个名为 trap 的函数，用于解决经典的“接雨水”问题。该问题要求计算给定整数数组（代表柱状图中各个柱子的高度）中可以接住的雨水量。以下是对代码的逐行解释：

1、函数定义:

var trap = function(height) {

定义了一个名为 trap 的函数，接受一个名为 height 的数组参数。

2、初始化变量:

let n = height.length;
let res = 0;

• n 用于存储数组 height 的长度。
• res 初始化为 0，用于累加可以接住的雨水总量。

3、边界条件检查:

if (n === 0) return 0;

如果数组长度为 0，直接返回 0，因为没有雨水可以接住。

4、初始化左右最大值数组:

let left_max = [], right_max = [];

• left_max 数组用于存储每个位置左侧的最大高度。
• right_max 数组用于存储每个位置右侧的最大高度。

5、填充左侧最大值数组:

left_max[0] = height[0];
for (let i = 1; i < n; i++) {
    left_max[i] = Math.max(left_max[i - 1], height[i]);
}

• 首先，将 left_max 的第一个元素设置为 height 的第一个元素。
• 然后，使用一个循环从第二个元素开始，每个元素的高度设置为它左侧元素的高度和当前元素高度中的较大者。

6、填充右侧最大值数组:

right_max[n - 1] = height[n - 1];
for (let i = n - 2; i >= 0; i--) {
    right_max[i] = Math.max(right_max[i + 1], height[i]);
}

• 首先，将 right_max 的最后一个元素设置为 height 的最后一个元素。
• 然后，使用一个循环从倒数第二个元素开始，每个元素的高度设置为它右侧元素的高度和当前元素高度中的较大者。

7、计算雨水量:

for (let i = 0; i < n; i++) {
    res += Math.min(left_max[i], right_max[i]) - height[i];
}

• 遍历整个 height 数组。
• 对于每个元素，计算左侧最大高度和右侧最大高度中的较小值，然后减去当前高度，得到当前位置可以接住的雨水量。
• 将这个值累加到 res 中。

8、返回结果:

return res;

返回计算得到的雨水总量。

总结

这个函数通过分别计算每个位置左右两侧的最大高度，然后取较小者减去当前高度，来确定每个位置可以接住的雨水量。这种方法的时间复杂度是 O(n)，因为每个数组元素只被访问一次。空间复杂度是 O(n)，因为使用了两个额外的数组来存储左右两侧的最大高度。