首页 > 试题广场 >

接雨水问题

[编程题]接雨水问题

热度指数：95285 时间限制：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]

输出

算法知识视频讲解

Java

牛客499848474号

import java.util.*;

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

* max water

* @param arr int整型一维数组 the array

* @return long长整型

public long maxWater (int[] arr) {

// write code here

if (arr.length == 0) {

return 0;

}

int left = 0;

int right = arr.length - 1;

int result = 0;

int lmax = arr[left];

int rmax = arr[right];

while (left < right) {

if (arr[left] < arr[right]) {

result += Math.max(0, lmax - arr[left]);

lmax = Math.max(lmax, arr[left]);

left++;

} else {

result += Math.max(0, rmax - arr[right]);

rmax = Math.max(rmax, arr[right]);

right--;

}

return result;

}

发表于 2025-10-22 20:11:07 回复(0)

Java

Sen🍓🍀

import java.util.*;

// @@@ 接雨水：双指针i,j初始位于两端, 水柱最高取min(a[i],a[j])
//            i,j总移动小的那端,向中心移动直到碰到更高的桶边更新两端大小关系
//            直至i,j相遇
public class Solution {

    public long maxWater (int[] arr) {
        if (arr.length <= 1) return 0;

        int i = 0, j = arr.length - 1, left = arr[i], right = arr[j];
        long res = 0;
        while (i < j) {
            // 左端更矮
            if (left <= right) {
                while (i < j && arr[i] <= left) { // 遇到更低的,有水
                    res += left - arr[i];
                    i++;
                }
                if (i == j) break;
                left = arr[i]; // 更新左端桶高
            }
            // 右端更矮 （处理同上）
            else {
                while (i < j && arr[j] <= right) {
                    res += right - arr[j];
                    j--;
                }
                if (i == j) break;
                right = arr[j];
            }
        }

        return res;
    }
}

发表于 2025-03-23 08:44:15 回复(0)

Java

做则必成的勇气和信心

public long maxWater (int[] arr) {
        // 双指针 每次只计算一个格子的
        int left=0;
        int right=arr.length-1;
        if(arr==null) return 0L;
        long ans=0;
        int maxL=0;
        int maxR=0;
        while(left<right){
            //每次维护中间的最大边界
            maxL=Math.max(maxL,arr[left]);
            maxR=Math.max(maxR,arr[right]);
            //判断哪边是较短的，统计水量
            if(maxR>maxL){
                ans=ans+(maxL-arr[left]);
                left++;
            }else{
                ans=ans+(maxR-arr[right]);
                right--;
            }
        }
        return ans;
    }

发表于 2023-07-24 10:20:16 回复(0)

Java

BlueProtocol

public class Solution {
    public long maxWater (int[] arr) {
        // write code here
        int length = arr.length;
        int left = 0;
        int right = length - 1;
        long sum = 0L;
        int lowMark = Math.min(arr[left], arr[right]);
        while (left < right) {
            if (arr[left] < arr[right]) {
                left++;
                if (arr[left] < lowMark) sum += lowMark - arr[left];
                else lowMark = Math.min(arr[left], arr[right]);
            } else {
                right--;
                if (arr[right] < lowMark) sum += lowMark - arr[right];
                else lowMark = Math.min(arr[left], arr[right]);
            }
        }
        return sum;
    }
}

发表于 2023-03-21 18:39:48 回复(0)

Java

wpcAlex

import java.util.*;


public class Solution {
    public long maxWater (int[] arr) {
        // write code here
        int l = 0, r = arr.length - 1;
        int ans = 0, lmax = 0, rmax = 0;
        while (l < r) {
            //找左右两边最高的高度
            lmax = Math.max(lmax, arr[l]);
            rmax = Math.max(rmax, arr[r]);
            //接雨水由最短的板子决定，计算雨量和移动短板
            if (lmax < rmax) {
                ans += lmax - arr[l];
                l++;
            } else {
                ans += rmax - arr[r];
                r--;
            }
        }
        return ans;
    }
}

发表于 2023-01-28 14:38:29 回复(0)

Java

五呀

我也不知道自己咋写的

import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        // write code here
        int left = 0;
        int right = 1;
        int temp= 0;
        int res = 0;
        while(right<arr.length){
            if(arr[left]>arr[right]){
                temp+=arr[left]-arr[right];
                right++;
            }else{
                res+=temp;
                temp =0;
                left = right;
                right++;
            }
        }
        if(temp == 0){
            return res;
        }
        int rever= arr.length-2;
        temp = 0;
        right--;
        while(rever>=left){
            if(arr[rever]<arr[right]){
                temp+=arr[right]-arr[rever];
                rever--;
            }else{
                res +=temp;
                temp=0;
                right = rever;
                rever--;
            }
        }
        return res;
    }
}

发表于 2022-11-22 21:34:50 回复(0)

Java

不卷了，就测开了

灵机一动，写出了非常简洁的代码，参考知乎大神 https://zhuanlan.zhihu.com/p/436613867 的做法

在力扣运行成功，时间100%

class Solution {
    public int trap(int[] height) {
        int l=0,r=height.length -1,lnum=height[l],rnum=height[r],res=0;
        while(l<r){
            if(lnum<=rnum){
                l++;
                res += Math.max(lnum-height[l],0);
                lnum = Math.max(lnum, height[l]);
            }
            else{
                r--;
                res += Math.max(rnum - height[r], 0);
                rnum = Math.max(rnum, height[r]);
            }
        }
        return res;
    }
}

发表于 2022-09-30 20:28:30 回复(0)

Java

ludvig

import java.util.ArrayList;

public class Solution {

public long maxWater (ArrayList<Integer> arr) {

int i = 0;

int j = arr.size()-1;

int sum = 0;

int min = Math.min(arr.get(i),arr.get(j));

while(i<j){

if(arr.get(i)<arr.get(j) && i<j){

while(arr.get(i)<=min){

sum =sum-arr.get(i)+min;

i++;

}

min = Math.min(arr.get(i),arr.get(j));

}else{

while(arr.get(j)<=min && i<j){

sum= sum-arr.get(j)+min;

j--;

}

min = Math.min(arr.get(i),arr.get(j));

}

return sum;

}

发表于 2022-09-29 11:54:27 回复(0)

Java

牛客520482770号

暴力求解

import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        // write code here
        if (arr == null || arr.length <= 2) {
            return 0;
        }
        int start = 0;
        List<Count> valid = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            Count between = between(start, arr);
            if (between.isValid()) {
                valid.add(between);
            }
            if (between.isOver()) {
                break;
            }
            start = between.getEnd();
        }
        long total = 0L;
        for (Count count : valid) {
            int min = Math.min(arr[count.getEnd()], arr[count.getStart()]);
            for (int i = count.getStart() + 1; i < count.getEnd(); i++) {
                total += min - arr[i];
            }
        }
        return total;
    }

    public Count between(int start, int[] arr) {
        Count count = new Count();
        if (start >= arr.length - 2) {
            count.setOver(true);
            return count;
        }

        if (arr[start + 1] >= arr[start]) {
            count.setValid(false);
            count.setEnd(start + 1);
            return count;
        }
        /*只剩下降趋势*/
        count.setStart(start);
        int flag = 1;
        int mid = start;
        while (mid < arr.length) {
            if (mid == arr.length - 1) {
                count.setOver(true);
                return count;
            }
            /*下降趋势*/
            if (arr[mid + 1] < arr[mid]) {
                /*第一次下降  最小值修改 end修改 继续*/
                if (flag == 1) {
                    count.setEnd(mid + 1);
                }
                /*第二次下降 有效区间 end修改*/
                if (flag == 2) {
                    count.setValid(true);
                    count.setEnd(mid);
                    break;
                }
            }
            /*等高*/
            if (arr[mid] == arr[mid + 1]) {
                count.setEnd(mid + 1);
            }
            /*增长趋势*/
            if (arr[mid + 1] > arr[mid]) {
                /*转折点*/
                if (flag == 1) {
                    count.setEnd(mid + 1);
                    count.setValid(true);
                    flag = 2;
                }
                /*不可能出现 flag==2 且是增长趋势*/
                count.setEnd(mid + 1);
            }
            mid++;
        }
        /*找寻更高的结束*/
        if (count.isValid() && arr[count.getStart()] >= arr[count.getEnd()]) {
            for (int i = count.getEnd(); i < arr.length; i++) {
                if (arr[i] >= arr[count.getStart()]) {
                    count.setEnd(i);
                    break;
                }
                if (arr[i] >= arr[count.getEnd()]) {
                    count.setEnd(i);
                }
            }
        }

        return count;
    }

    public static class Count {
        int start ;
        int end;
        boolean valid;
        boolean over;

        public int getStart() {
            return start;
        }

        public void setStart(int start) {
            this.start = start;
        }

        public int getEnd() {
            return end;
        }

        public void setEnd(int end) {
            this.end = end;
        }

        public boolean isValid() {
            return valid;
        }

        public void setValid(boolean valid) {
            this.valid = valid;
        }

        public boolean isOver() {
            return over;
        }

        public void setOver(boolean over) {
            this.over = over;
        }
    }
}

发表于 2022-09-19 17:11:29 回复(0)

Java

牛客238214010号

public long maxWater (int[] arr) {
// write code here
long count = 0;
int j;
int i=0;
int k=1 ;
for( i=0 ;i <arr.length;){
for(j = i+1;j<=arr.length-1;j++){
if(arr[i]>=arr[j]){
count+= arr[i]-arr[j];
i++;
}
else {
k = 0;
i = j;
break;
}

}

}
return count;
}
}

发表于 2022-09-09 10:30:10 回复(1)

Java

花遍人间

import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        // write code here
        if (arr.length < 3) return 0;
        int le = 0, ri = arr.length - 1;
        int maxl = 0, maxr = 0, res = 0;
        while (le < ri) {
            maxl = Math.max(maxl, arr[le]);
            maxr = Math.max(maxr, arr[ri]);
            //
            res += maxl < maxr ? maxl - arr[le++] : maxr - arr[ri--];
        }
        return res;
    }
}

发表于 2022-09-02 22:36:11 回复(0)

Java

yxjing

import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        // write code here
        int V=0;
        int[] leftmax=new int[arr.length];
        int[] rightmax=new int[arr.length];
        leftmax[0]=arr[0];
        rightmax[arr.length-1]=arr[arr.length-1];
        for(int i=1;i<=arr.length-1;i++){
            leftmax[i]=Math.max(leftmax[i-1],arr[i]);
        }
        for(int i=arr.length-2;i>=0;i--){
            rightmax[i]=Math.max(rightmax[i+1],arr[i]);
        }
        for(int i=0;i<=arr.length-1;i++){
            if(leftmax[i]!=arr[i]&&rightmax[i]!=arr[i]){
                V=V+Math.min(leftmax[i],rightmax[i])-arr[i];
            }
        }
        return V;
    }
    
}

发表于 2022-08-18 20:01:37 回复(0)

Java

牛客用户007

import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        // write code here
        int left = 0, right = arr.length - 1;
        int sum = 0, height = 0;
        while (left < right) {
            if (arr[left] < arr[right]) {
                height = Math.max(height, arr[left]);
                sum = sum + height - arr[left];
                left ++;
            } else {
                height = Math.max(height, arr[right]);
                sum = sum + height - arr[right];
                right--;
            }
        }
        return sum;
    }
}

发表于 2022-08-03 11:50:07 回复(0)

Java

Oliverrrr

看了答案的思路，然后自己写的，发现和答案的写法好像不太一样❓（不过讨论里有和我一样思路的）

开始想了半天怎么用Deque之类的来实现，然后发现没用到双指针，并且想法越来越复杂，直到放弃......

让我缓缓，等会再去看下答案的写法🥲

public long maxWater5 (int[] arr) {
    long res = 0;
    int i = 0, j = arr.length - 1;
    while (i < j) {
        long min = Math.min(arr[i], arr[j]);    // 保存边界中的较小值
        if (arr[i] < arr[j]) {  // 若「左边界」较小，i指针右移计算蓄水量
            while (arr[++i] < min) res += (min - arr[i]);   // 一次性移动完毕，到第一个高度 ≥ 左边界的柱子
        } else {    // 同理，「右边界」对称移动
            while (arr[--j] < min) res += (min - arr[j]);
        }
    }
    return res;
}

发表于 2022-06-17 22:47:57 回复(0)