首页 > 试题广场 >

接雨水问题

[编程题]接雨水问题
  • 热度指数:92101 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个整形数组arr,已知其中所有的值都是非负的,将这个数组看作一个柱子高度图,计算按此排列的柱子,下雨之后能接多少雨水。(数组以外的区域高度视为0)


数据范围:数组长度 ,数组中每个值满足 ,保证返回结果满足
要求:时间复杂度
示例1

输入

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

输出

5 

说明

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

输入

[4,5,1,3,2]

输出

2 
// 从短柱子的那一边开始做移动操作 
public class Solution {
    public long maxWater (int[] arr) {
        int n = arr.length;
        int idx1 = 0, point1 = 0;
        int idx2 = n - 1, point2 = n - 1;
        long sum = 0;
        while (point1 != point2) {
            if (arr[idx1] > arr[idx2]) {
                point2--;
                if (arr[idx2] > arr[point2]) {
                    sum += arr[idx2] - arr[point2];
                } else {
                    idx2 = point2;
                }
            } else {
                point1++;
                if (arr[idx1] > arr[point1]) {
                    sum += arr[idx1] - arr[point1];
                } else {
                    idx1 = point1;
                }
            }
        }
        return sum;
    }
}

发表于 2021-08-14 11:40:40 回复(0)
时间空间双98% 解法。从左往右找桶,累加容积;再从右往左找桶,累加容积。
public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    
    public long maxWater (int[] arr) {
        // write code here
        int vol = 0,left = 0, right = arr.length - 1;
        while( left < right){
            //左边往右找,高度比当前高就能成桶
            int leftSum = 0;
            for(int i = left + 1; i <= right ; i ++){
                //成桶
                if(arr[i] >= arr[left]){
                    //累加容积(容积 = 短板高度 * 长度 - 不能盛水的容积)
                    vol += arr[left] * ( i - left + 1 - 2) - leftSum;
                    //替换left为当前点
                    left = i;
                    leftSum = 0;
                    continue;
                }
                //统计中间不能盛水的地方
                leftSum += arr[i];
            }
            //右边同理,往左找
            int rightSum = 0;
            for(int i = right - 1; i >= left ; i --){
                //成桶
                if(arr[i] >= arr[right]){
                    //累加容积
                    vol += arr[right] * (right - i + 1 - 2) - rightSum;
                    //替换right为当前点
                    right = i;
                    rightSum = 0;
                    continue;
                }
                //统计中间不能盛水的地方
                rightSum += arr[i];
            }
        }
        return vol;
    }
}

发表于 2022-04-16 15:45:02 回复(0)

代码提交成功平均运行 耗时 450 毫秒左右

1.首先求数组最大值a,定位索引位置;
2.根据最大值左右两边拆分数组,求左右两边数组最大值分别为多少,
3.左右两边最大值与数组最大值a之间的差值就是雨水;
4.同理循环上述即可;
# -*- coding:utf-8 -*-
def max_yu(list_yu):
    max_n = 0
    i = 0
    max_zhu_inedx = []
    len_n = len(list_yu)
    max_zhu = max(list_yu)
    max_zhu_wzhi_c = list_yu.index(max_zhu)
    max_zhu_count = list_yu.count(max_zhu)
    if max_zhu_count == 1 and list_yu.count(list_yu[0]) == len_n-1:
        print(max_n)
        return max_n
    else:
        if max_zhu_count > 1:
            while i < len_n:
                if max_zhu == list_yu[i]:
                    max_zhu_inedx.append(i)
                i += 1
            min_zhu_index = min(max_zhu_inedx)
            max_zhu_index = max(max_zhu_inedx)
            if max_zhu_index - min_zhu_index == 1:
                max_n = 0
            else:
                min_zhu_index_lshi = min_zhu_index
                while min_zhu_index_lshi < max_zhu_index:
                    max_n = max_n + max_zhu - list_yu[min_zhu_index_lshi]
                    min_zhu_index_lshi += 1
                chushi = max_zhu_index
                while chushi < len_n:
                    max_f1_list = list_yu[chushi + 1:]
                    if len(max_f1_list) != 0:
                        max_f1 = max(max_f1_list)
                        max_f1_inedx = max_f1_list.index(max_f1)
                        if max_f1_inedx == 0:
                            chushi += 1
                        else:
                            j = 0
                            while j < max_f1_inedx:
                                max_n = max_n + max_f1 - max_f1_list[j]
                                j += 1
                            chushi = max_f1_inedx + 1 + chushi
                    else:
                        chushi += 1
                chushi = min_zhu_index
                while chushi > 0:
                    max_f2_list = list_yu[:chushi]
                    max_f2 = max(max_f2_list)
                    max_f2_inedx = max_f2_list.index(max_f2)
                    if max_f2_inedx == len(max_f2_list) - 1:
                        chushi -= 1
                    else:
                        j = max_f2_inedx
                        while j < len(max_f2_list):
                            max_n = max_n + max_f2 - max_f2_list[j]
                            j += 1
                        chushi = max_f2_inedx
                return max_n


        else:
            max_zhu_inedx.append(max_zhu_wzhi_c)
        if len(max_zhu_inedx) == 1:
            chushi = max_zhu_wzhi_c
            while chushi < len_n:
                max_f1_list = list_yu[chushi+1:]
                if len(max_f1_list) != 0:
                    max_f1 = max(max_f1_list)
                    max_f1_inedx = max_f1_list.index(max_f1)
                    if max_f1_inedx == 0:
                        chushi += 1
                    else:
                        j = 0
                        while j < max_f1_inedx:
                            max_n = max_n + max_f1 - max_f1_list[j]
                            j += 1
                        chushi = max_f1_inedx + 1 + chushi
                else:
                    chushi += 1
            chushi = max_zhu_wzhi_c
            while chushi > 0:
                max_f2_list = list_yu[:chushi]
                max_f2 = max(max_f2_list)
                max_f2_inedx = max_f2_list.index(max_f2)
                if max_f2_inedx == len(max_f2_list) - 1:
                    chushi -= 1
                else:
                    j = max_f2_inedx
                    while j < len(max_f2_list):
                        max_n = max_n + max_f2 - max_f2_list[j]
                        j += 1
                    chushi = max_f2_inedx
            return max_n

max_yu([3,1,2,5,2,4]  )


发表于 2022-02-09 13:11:37 回复(0)

这个题乍一看没有思路,但仔细研究就会发现,能不能装雨水主要取决于有没有“上下楼梯”的情况。我们假设有个数组是12321.那么最高的元素是3,可以看到最高元素的左边如果满足“上楼梯”的情况,是装不到水的。同样,右边元素满足“下楼梯”也是装不到水的。那么如何判断“上楼梯”“下楼梯”的情况呢?只需要设置两个指针left,right。让这两个指针都从端点出发,在最高元素的左半部分,就让left不动,right向右移动。雨水量就是arr[left]>arr[right]时,也就是“下楼梯”,arr[left]-arr[right]就是接的雨水量。当arr[left]-arr[right]<0时,只需要再从当前right位置继续计算雨水量就行了。当然,在右半部分,只需保持right不动,left左移即可。

import java.util.*;
public class Solution {
    public long maxWater (int[] arr) {
        int len = arr.length;
        if(len<=1)return 0;
        int top=arr[0],left=0,right,maxindex=0;
        long count=0;
        for(int j=0;j<len;++j){
            if(top<arr[j]){
                maxindex = j;
                top=arr[j];
            }
        }
        for(left =0,right=0;right<maxindex;){
            if(arr[left]>=arr[right]){
                count = count+arr[left]-arr[right];
                right++;
            }
            else left=right;
        }
        for(left =len-1,right=len-1;left>maxindex;){
            if(arr[left]<=arr[right]){
                count = count+arr[right]-arr[left];
                left--;
            }
            else right=left;
        }
        return count;
    }
}
发表于 2021-09-27 20:24:05 回复(1)
双指针,虽然每次i与j的值都是还没加入到ans里的值。但是每次更新都是变动的是leftMax与rightMax小的那一边的值。所以i与j会在最高峰相遇。此时while(i<j)与while(i<=j)会是一样的结果。
class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        // write code here
        int i=0;
        int j=arr.size()-1;
        long long ans=0;
        int leftMax=arr[i];
        int rightMax=arr[j];
        //
        while(i<=j){
            if(leftMax<rightMax){
                ans+=leftMax-arr[i];
                i++;
                leftMax=std::max(leftMax,arr[i]);
            }else{
                //这里leftMax>=rightMax,否则循环可能出不去
                ans+=rightMax-arr[j];
                j--;
                rightMax=std::max(rightMax,arr[j]);
            }
        }
        
        return ans;
    }
};

发表于 2021-09-18 10:45:26 回复(0)
public class Solution {
    public long maxWater (int[] arr) {
        // write code here
        int len = arr.length;
        int[] left = new int[len];
        int[] right = new int[len];
        
        left[0] = arr[0];
        for(int i = 1; i < len; i++){
            left[i] = Math.max(arr[i], left[i-1]);
        }
        
        right[len-1] = arr[len-1];
        for(int i = len - 2; i >= 0; i--){
            right[i] = Math.max(arr[i], right[i+1]);
        }
        
        long ans = 0;
        for(int i = 0; i < arr.length; i++){
            ans += Math.min(left[i], right[i]) - arr[i];
        }
        return ans;
    }
}

发表于 2021-09-14 20:24:03 回复(0)
import java.util.*;


public class Solution {
    public long maxWater (int[] arr) {
        long sum=0;
        int[] max_left=new int[arr.length],max_right=new int[arr.length];
        for(int i=1;i<arr.length-1;i++){
            max_left[i] = Math.max(max_left[i-1],arr[i-1]);
        }
        for(int i=arr.length-2;i>=0;i--){
            max_right[i] = Math.max(max_right[i+1],arr[i+1]);
        }

        for(int i=1;i<arr.length-1;i++){            
            sum += Math.max(0,Math.min(max_left[i],max_right[i])-arr[i]);
        }
        return sum;
    }
}
发表于 2021-08-22 20:04:39 回复(0)
long long maxWater(vector<int>& arr) {
        // write code here
        int n=arr.size();
        long long maxWater=0;
        int l=0,r=n-1;
        long long minWater=min(arr[l],arr[r]);

        while(l<r){
            if(arr[l]>arr[r]){
                r--;
                if(arr[r]>=minWater){
                    minWater=min(arr[l],arr[r]);
                }else{
                    maxWater+=minWater-arr[r];
                }
            }else{
                l++;
                if(arr[l]>=minWater){
                    minWater=min(arr[l],arr[r]);
                }else{
                    maxWater+=minWater-arr[l];
                }
            }
        }
        return maxWater;
    }

发表于 2021-07-15 10:30:50 回复(0)
class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& height) {
      const int n = height.size();
      int peakIndex = max_element(begin(height), end(height)) - begin(height);

      long ans = 0;
      int leftMostBar = 0;
      for (int i = 0; i < peakIndex; ++i) {
        if (height[i] > leftMostBar)
          leftMostBar = height[i];
        else
          ans += leftMostBar - height[i];
      }

      int rightMostBar = 0;
      for (int i = n - 1; i > peakIndex; --i) {
        if (height[i] > rightMostBar)
          rightMostBar = height[i];
        else
          ans += rightMostBar - height[i];
      }

      return ans;
    }
};

发表于 2021-07-08 13:50:04 回复(0)
算法思想:

a[left, right] 是一个水槽, 递归的看,可能中间存在某个mid, a[left, mid]也是水槽,a[mid, right]也是水槽,那么怎么解决这个递归问题呢?

本人的方法是用一把刀横着去切水槽:sum表示水槽容积

1.假设用一把 刀 横着去切这个水槽 a[left, right] 那么从哪边开始切呢?当然是从小的一边开始切

if a[left] <= a[right] 从左边向右切一刀水槽:

    怎么切?没有遇到挡住的障碍,说明可以装水,一路切过去,同时计算sum += a[left] - a[l]

if a[left] > a[right] 从右边向左切一刀水槽:

    怎么切?没有遇到挡住的障碍,说明可以装水,一路切过去,同时计算sum += a[right] - a[r]

2.切完一次,left 和 right 重新移到递归小水槽的两边, 于是又递归成了切水槽问题(计算水槽容积问题),返回 1 计算,直到 l = r

整个数组遍历一次,时间复杂度:O(n) 空间复杂度O(1)
class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        int l =0, r = arr.size()-1;
        long long sum=0; //注意要long long 否则很可能加法溢出
        while(l<r){//左右不等,没砍完
            if(arr[l] <= arr[r]){ // 左边比右边小,从左边开始砍
                int left = arr[l]; //基准
                while(l+1<r && arr[l+1]< left){ //如果右边一个位置比基准矮,刀无阻碍
                    sum += (left-arr[l+1]); //刀下方可以装水
                    l++;
                }
                l++; //刀遇到到第一个碰瓷(碰刀)的柱子
            }
            else{ //否则从右边开始切
                int right = arr[r]; //以右边最低为基准
                while(r-1>l && arr[r-1] < right){//如果左边一个位置比基准矮,刀无阻碍
                    sum += (right -arr[r-1]); //刀下方装水
                    r--;
                }
                r--; //向左移移到第一个碰瓷(碰刀)的柱子
            }
        }
        return sum;
    }
};


编辑于 2021-03-23 22:56:19 回复(1)
解题思路:使用双指针,外循环终止条件为左指针与右指针相遇,内循环为,如果左边值小,则从左到右遍历,反之从右到左遍历
import java.util.*;
public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        // write code here
        //定义一个用来累加的变量
        long count = 0L;
        //定义起始的左边界
        int from = 0;
        //定义一个起始的右边界
        int to = arr.length - 1;
        while(from < to){
            //找到最小的边界
            int min=Math.min(arr[from],arr[to]);
            while(from<to&&min>=arr[from]){
                count+=min-arr[from];
                from++;
            }
            while(from<to&&min>=arr[to]){
                count+=min-arr[to];
                to--;
            }
        }
 
        return count;
    }
}
发表于 2021-03-15 09:49:16 回复(0)
/**
 * max water
 * @param arr int整型一维数组 the array
 * @param arrLen int arr数组长度
 * @return long长整型
 */
long long maxWater(int* arr, int arrLen ) {
    if (arrLen <= 2) {
        return 0;
    }
    long long res = 0;
    int left = 0;
    int right = arrLen - 1;
    int maxLeft = arr[left];
    int maxRight = arr[right];
    while (left < right) {
        if (maxLeft < maxRight){
            left++;
            if (maxLeft < arr[left]) {
                maxLeft = arr[left];
            } else {
                res += maxLeft - arr[left];
            }
        } else {
            right--;
            if (maxRight < arr[right]) {
                maxRight = arr[right];
            } else {
                res += maxRight - arr[right];
            }
        }
    }
    return res;
}

发表于 2021-02-28 17:03:47 回复(0)
import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        // write code here
        long res=0;
        int left_Height,right_Height;
        int left=0,right=arr.length-1;
        while(left<right){
            left_Height=arr[left];
            right_Height=arr[right];
            if(left_Height<right_Height){
                while(left<right&&arr[left]<=left_Height){
                    res+=left_Height-arr[left];
                    left++;//left++更新左侧最高的柱子,同下面right--对应,镜像,当while条件不满
                                               //足时,结束当前计算循环
                }
            }else{
                while(left<right&&arr[right]<=right_Height){
                    res+=right_Height-arr[right];
                    right--;
                }
            }
        }
        return res;
    }
}
最好画个简单的柱图跟着代码的逻辑走一遍,就会恍然大悟,哈哈
编辑于 2020-12-06 18:19:38 回复(2)
class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr)
    {
        int l = 0, r = arr.size() - 1;
        long long ans = 0;
        int lmax = 0, rmax = 0;
        while(l < r)
        {
            lmax = max(lmax, arr[l]);
            rmax = max(rmax, arr[r]);
            if(lmax < rmax)
            {
                ans += lmax - arr[l++];
            }
            else
            {
                ans += rmax - arr[r--];
            }
        }
        return ans;
    }
};

找水平线,不断更新水平线
发表于 2020-12-04 10:30:29 回复(0)
class Solution
{
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long maxWater(vector<int> &arr)
    {
        // write code here
        int n = arr.size();
        if (n <= 2)
            return 0;
        int i = 0, j = n - 1, left = arr[0], right = arr[n - 1];
        long long sum_val = 0;
        while (i < j)
        {
            if (left < right)
            {
                i++;
                if (arr[i] >= left)
                {
                    left = arr[i];
                    continue;
                }
                sum_val += (left - arr[i]);
            }
            else
            {
                j--;
                if (arr[j] > right)
                {
                    right = arr[j];
                    continue;
                }
                sum_val += (right - arr[j]);
            }
        }
        return sum_val;
    }
};


发表于 2020-09-27 11:14:52 回复(1)
public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        if (arr == null || arr.length == 0) return 0L;
        long ans = 0;
        int left = 0, right = arr.length - 1;
        int lmax = arr[left], rmax = arr[right];
        while (left < right) {
            lmax = Math.max(arr[left], lmax);
            rmax = Math.max(arr[right], rmax);
            if (lmax <= rmax) ans += lmax - arr[left++];
            else ans += rmax - arr[right--];
        }
        return ans;
    }
}

发表于 2021-04-20 01:18:53 回复(0)
思路:
1.按照反例思想,假设两个柱子(包括两个柱子)中间所有位置都可以存水,按照两个柱子里面,较低的那一根的高度,计算总存水量。接着减去,两个柱子间所有不可存水的块的数量(即数组里,两个位置间的值的和,这里面要包括两个较低柱子高度),最终得到两个柱子之间的可存水量
2.寻找到最高的柱子的位置,从左向它去不断的找比左侧高的柱子,然后迭代更新左侧低柱子位置。
3.从右向最高柱子,进行同样的操作。
4.最终相加,完成总存水量的计算。
(注意:最后算总和的时候,要考虑数的溢出问题,转成long这个很关键)
class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
    */
    void find_max(vector<int> arr, int &index) //遍历一遍找到最大的值,以及最大的索引
    {
        int max_num = arr[0];
        index = 0;
        int temp_max = 0;
        for (int i = 1; i < arr.size(); i++)
        {
            temp_max = arr[i];
            if (temp_max > max_num)
            {
                max_num = temp_max;
                index = i;
            }
        }
    }
    
    long long maxWater(vector<int>& arr) {
        long long temp_block = arr[0];
        long long temp_whole = 0;
        int max_index = 0;
        if (arr.size() == 1)
            return 0;
        find_max(arr, max_index);  //先找到最大值的位置
        
        //从左向最大值,寻找最多存水
        int left = 0;
        long long lf_sum = 0;
        temp_block = arr[0];
        temp_whole = 0;
        for (int i = 1; i <= max_index; i++) 
        {
            if (arr[i] >= arr[left]) //比左侧的相等,或者高了,来计算一波存水量
            {
                temp_whole = long(arr[left]) * (i - left + 1); //假设整个区间都可以存水
                temp_block += arr[left];
                lf_sum = lf_sum + (temp_whole - temp_block); //减去中间被占用到的存水的位置
                temp_block = arr[i];
                left = i;
            }
            else  //没有左侧那么高,直接累加起来
                temp_block += arr[i];
        }
        
        //从右向最大值,寻找最多存水
        int right = arr.size() - 1;
        long long rh_sum = 0;
        temp_block = arr[right];
        temp_whole = 0;
        for (int i = right - 1; i >= max_index; i--)
        {
            if (arr[i] >= arr[right]) //比右侧的相等,或者高了,来计算一波
            {
                temp_whole = long(arr[right]) * (right - i + 1);  //假设整个区间都可以存水
                temp_block += arr[right];
                rh_sum = rh_sum + (temp_whole - temp_block); //减去中间被占用到的存水的位置
                temp_block = arr[i];
                right = i;
            }
            else  //没有那么高,直接累加起来
                temp_block += arr[i];
        }
        //最后返回两侧存水之和
        return (lf_sum + rh_sum);
    }
};


发表于 2020-12-30 18:23:42 回复(0)
将数组中每个位置上的累加起来就是总的水量
首先求容器边界,
然后使用双指针,
分别从两边往中间扫描,
当左边的高度小于右边的高度时,左指针++,
如果此时当前位置的高度小于容器的边界高度,这个位置上方有水,进行水量累加。
反之,则右指针向左扫描-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)
题意与python题解
1、题意(题解区某大佬图)
与力扣 42.接雨水 一致


2、python题解
①python牛客有问题,返回1都能超时。以下题解已通过本地IDE
②动态编程法:遍历两遍,从左往右遍历保存当前最大值,从右往左遍历保存当前最大值,然后容水量为 两次遍历最大值中的最小值减去当前arr[i]。累加起来即可。(题解区某大佬C++改写)
class Solution:
    def maxWater(self , arr ):
        # write code here
        le = len(arr)
        l = list([0] * le)
        r = list([0] * le)
        
        l[0] = arr[0]
        r[le - 1] = arr[le - 1]
        for i in range(1, le):
            l[i] = max(l[i - 1], arr[i])
            r[le - i - 1] = max(r[le - i], arr[le - i - 1])
        
        res = 0
        for i in range(1, le - 1):
            if min(l[i], r[i]) - arr[i] > 0:
                res += min(l[i], r[i]) - arr[i]
        return res


③双指针(力扣Java官解改写)

我们先明确几个变量的意思:

left_max:左边的最大值,它是从左往右遍历找到的
right_max:右边的最大值,它是从右往左遍历找到的 left:从左往右处理的当前下标 right:从右往左处理的当前下标

定理一:在某个位置i处,它能存的水,取决于它左右两边的最大值中较小的一个。

定理二:当我们从左往右处理到left下标时,左边的最大值left_max对它而言是可信的,但right_max对它而言是不可信的。(见下图,由于中间状况未知,对于left下标而言,right_max未必就是它右边最大的值)

定理三:当我们从右往左处理到right下标时,右边的最大值right_max对它而言是可信的,但left_max对它而言是不可信的。



对于位置left而言,它左边最大值一定是left_max,右边最大值“大于等于”right_max,这时候,如果left_max<right_max成立,那么它就知道自己能存多少水了。无论右边将来会不会出现更大的right_max,都不影响这个结果。 所以当left_max<right_max时,我们就希望去处理left下标,反之,我们希望去处理right下标
class Solution:
    def maxWater(self, arr ):
        left, right, res, left_max, right_max = 0, len(arr) - 1, 0, 0, 0
        while left < right:
            if arr[left] < arr[right]:
                if arr[left] > left_max:
                    left_max = arr[left]
                else:
                    res += left_max - arr[left]
                left += 1
            else:
                if arr[right] > right_max:
                    right_max = arr[right]
                else:
                    res += right_max - arr[right]
                right -= 1
        return res


编辑于 2021-03-23 14:09:41 回复(1)
双指针 i,j分别从两头向中间遍历,当i,j相同时循环终止。
思路:
1. 假设只有左右边界,中间的墙都是0,那么盛水量以最低的边界为准,所以后面更新边界的过程中,左边界更低就++i,右边界更低就--j 
2. 实际情况中间可能存在比边界更高墙,从最低的边界遍历,比边界低的情况下,直接累加水量,遇到比边界更高的墙,说明当前坐标下的墙无法盛水,直接更新为边界。
public class Solution {
    public long maxWater (int[] arr) {
        int l = 0, r = arr.length - 1, i = l, j = r;
        long v = 0;
        while (i < j) {
            if (arr[l] < arr[r]) {
                if (arr[++i] < arr[l]) {
                    v += arr[l] - arr[i];
                } else {
                    l = i;
                }
            } else {
                if (arr[--j] < arr[r]) {
                    v += arr[r] - arr[j];
                } else {
                    r = j;
                }
            }
        }
        return v;
    }
}


发表于 2021-01-31 13:54:01 回复(6)

问题信息

难度:
215条回答 9923浏览

热门推荐

通过挑战的用户

接雨水问题