当前位置：首页 > article >正文

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

article 2024/9/20 9:42:08

文章目录

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);