day-20 接雨水

参考了答案。。。。。。

思路：用两个数组分别记录height[i]左右两边最高的墙（i0和iheight.length-1不可能存水）遍历heigthi，如果Math.min(maxl[i],maxr[i])>height[i] 则当前位置可存储 Math.min(maxl[i],maxr[i])-height[i]的水。

code:

class Solution {

    public int trap(int[] height) {

      int maxl[]=new int[height.length];
      int maxr[]=new int[height.length];
      for(int i=1;i<height.length;i++){

        maxl[i]=Math.max(maxl[i-1],height[i-1]);
      }
      for(int i=height.length-2;i>=0;i--){

        maxr[i]=Math.max(maxr[i+1],height[i+1]);
      }
      int ans=0;
      for(int i=1;i<height.length-1;i++){

        if(Math.min(maxl[i],maxr[i])>height[i])
        ans+=Math.min(maxl[i],maxr[i])-height[i];
      }
      return ans;
    }
}

原文链接: https://blog.csdn.net/qq_53568730/article/details/136727906

目录