每天一道算法题（七）——求一个数组中最多能存储多少雨水（困难）

本文主要是介绍每天一道算法题（七）——求一个数组中最多能存储多少雨水（困难），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

1、问题
2、示例
3、解决方法
- （1）方法1——双指针
总结

1、问题

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

2、示例

示例 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

3、解决方法

（1）方法1——双指针

let height = [0,1,0,2,1,0,1,3,2,1,2,1];
let trap = function(height) {// 1-1: 定义返回多少个单位雨水的值, 左指针, 右指针let sum = 0, left = 0, right = height.length - 1;// 1-2: 定义左指针最大值,右指针最大值let leftMax = 0, rightMax = 0;// 2-0:当两个指针没有相遇的时候while(left< right) {// 2-1: 根据不同的指针更新当前左右指针下标在height数组中的最大值leftMax = Math.max(leftMax, height[left])rightMax = Math.max(rightMax, height[right])// 2-2-1:当左指针获取的值 小于  右指针获取的值if(height[left] < height[right]){sum += leftMax - height[left] // 说明： lfetMax < rightMax ,则下标left的雨水量等于 leftMax - height[left]left++ // 说明： 0 < 1  =>  1 < 1 (也就是获取左边数据的下一位再次对比)} else {// 2-2-2:当左指针获取的值 大于等于  右指针获取的值sum += rightMax - height[right] // 说明： lfetMax >= rightMax ,则下标right的雨水量等于 rightMax - height[right]right-- // 说明2:  1 >= 1 =>  1 >= 2}}console.log('max', sum); // 6
};
trap(height);