接雨水问题

[编程题]接雨水问题

热度指数：92095 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0)

数据范围：数组长度 $0 \le n \le 2\times10^5$ ，数组中每个值满足 $0 < val \le 10^9$ ，保证返回结果满足 $0 \le val \le 10^9 \$

要求：时间复杂度 $O(n)$

示例1

输入

[3,1,2,5,2,4]

输出

说明

数组 [3,1,2,5,2,4] 表示柱子高度图，在这种情况下，可以接 5个单位的雨水，蓝色的为雨水 ，如题面图。

示例2

输入

[4,5,1,3,2]

输出

算法知识视频讲解

Javascript

牛客140967527号

练习第一天遇到了这个问题，用的最简单粗暴的办法，优化了下勉强能通过。

function maxWater( arr ) {
    const size = arr.length;
    let maxH = arr[0];
    let maxIdx = 0;
    let sum = 0;
    
    const topList = arr.map((v, idx) => ({ v, idx })).sort((i1, i2) => {
        const v1 = i1.v, v2 = i2.v;
        const o1 = i1.idx, o2 = i2.idx;
        return (v1 !== v2
          ? (v1 < v2 ? 1 : -1)
          : (o1 < o2 ? -1 : 1)
        );
    });
    
    const getWaterV = (startIdx, endIdx) => {
        const startH = Math.min(arr[startIdx], arr[endIdx]);
        let sum = 0;
        
        for (let i = startIdx + 1; i < endIdx; i++) {
            const v = startH - arr[i];
            sum += v;
        }
        
        return sum;
    };
    
    const isRestLowerThenMe = (startIdx) => {
        const curH = arr[startIdx];
        const size = topList.length;
        let result = true;
        
        // 查找 top 列表中值比当前值大的是否位于待检查元素左侧（index < startIdx);
        for (let i = 0; i < size; i++) {
            const {v, idx} = topList[i];
            if (v > curH && idx > startIdx) {
                result = false;
                break;
            }
            
            if (idx === startIdx) {
                break;
            }
        }
        
        return result;
    };
    
    for (let i = 1; i < size; i++) {
        const h = arr[i];
        const isHigherThenMax = h >= maxH;
        
        if (isHigherThenMax || isRestLowerThenMe(i)) {
            sum += getWaterV(maxIdx, i);
            maxH = h;
            maxIdx = i;
        }
    }
    
    return sum;
}

发表于 2021-12-04 12:27:45 回复(0)

Javascript

天网-__-

装水的多少取决于左右两边高度的最小值lmax和rmax，如果左边矮，这从左边开始+1的位置一定能装lmax-arr[i]的水且只能装怎么多水，右边rmax保证一定能装怎么多不会从右边溢出，左边lmax保证只能装怎么多否则会从左边溢出

function maxWater( arr ) {
    if (arr.length <= 2) return 0;
    let l = 0, r = arr.length-1, lmax = 0, rmax = 0, res = 0;
    while(l < r) {
        lmax = Math.max(arr[l], lmax);
        rmax = Math.max(arr[r], rmax);
        if (lmax < rmax) {
            res += lmax - arr[l++];
        } else {
            res += rmax - arr[r--];
        }
    }
    return res;
}

发表于 2021-11-27 10:03:05 回复(0)

JavaScript

一直赢好无奈

之前按扫描行算超时了。按列算

function maxWater( arr ) {
    // write code here
    let sum = 0 , lMax = [] , rMax = [] , row = arr.length;
    for(let i=0 ; i < row ; i++) 
    {
    	lMax[i] = Math.max(lMax[i-1] || 0,arr[i]);
    	rMax[row-i-1] = Math.max(rMax[row-i] || 0,arr[row-i-1]);
    }
    for(let i=1 ; i < row-1 ; i++)
    {
        sum += Math.min(rMax[i] , lMax[i]) - arr[i];   
    }
    return sum;
}

发表于 2021-04-29 20:38:03 回复(0)

JavaScript

别卷啦！

将数组中每个位置上的累加起来就是总的水量

首先求容器边界,
然后使用双指针,
分别从两边往中间扫描,
当左边的高度小于右边的高度时,左指针++,
如果此时当前位置的高度小于容器的边界高度,这个位置上方有水,进行水量累加。
反之，则右指针向左扫描-1。

function maxWater( arr ) {
    // write code here
 if(arr == null || arr.length<3) return 0
    let l = 0,r = arr.length-1, area = 0
    let min = Math.min(arr[l],arr[r])
    while(l<r){
        if(arr[l]<arr[r]){
            l++
            if(arr[l]<min){
                area += min - arr[l]
            }else {
                min = Math.min(arr[l],arr[r])
            }
        }else{
            r--
            if(arr[r]<min){
                area +=min-arr[r]
            }else {
                min = Math.min(arr[r],arr[l])
            }
        }
    }
    return area
}

编辑于 2021-01-13 15:59:55 回复(6)