leetcode42 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [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

思路1：正着遍历求出代表左边最大值的数组，倒着遍历求出代表右边最大值的数组

每个位置的雨水就是左右低的那个-自己

注意：可能减出负数，这种情况答案为0.

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     
 public int trap(int[] height) {
     
    
   

    

     

    
    

     
 int len=height.length;
     
    
   

    

     

    
    

     
 if(len==0){
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int[] left=new int[len];
     
    
   

    

     

    
    

     
 int[] right=new int[len];
     
    
   

    

     

    
    

     

       left[0]=height[0];
     
    
   

    

     

    
    

     
 for(int i=1;i<len;i++){
     
    
   

    

     

    
    

     

       left[i]=Math.max(height[i],left[i-1]);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       right[len-1]=height[len-1];
     
    
   

    

     

    
    

     
 for(int i=len-2;i>=0;i--){
     
    
   

    

     

    
    

     

       right[i]=Math.max(height[i],right[i+1]);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int ans=0;
     
    
   

    

     

    
    

     
 for(int i=1;i<len-1;i++){
     
    
   

    

     

    
    

     

       ans+=Math.max(0,Math.min(left[i-1],right[i+1])-height[i]);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return ans;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

思路2：

双指针，优势是空间O(1)

我实在不想写解释了/

  

   

    

     

    
    

     

      public class Solution {
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 public int trap(int[] height) {
     
    
   

    

     

    
    

     
 int len = height.length;
     
    
   

    

     

    
    

     
 if (len < 3) {
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 int res = 0;
     
    
   

    

     

    
    

     
 int leftMax = height[0];
     
    
   

    

     

    
    

     
 int rightMax = height[len - 1];
     
    
   

    

     

    
    

     
 // 头和尾都不存雨水
     
    
   

    

     

    
    

     
 int left = 1;
     
    
   

    

     

    
    

     
 int right = len - 2;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 while (left <= right) {
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 int minVal = Math.min(leftMax, rightMax);
     
    
   

    

     

    
    

     
 if (minVal == leftMax) {
     
    
   

    

     

    
    

     
 if (minVal > height[left]) {
     
    
   

    

     

    
    

     

       res += minVal - height[left];
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       leftMax = Math.max(leftMax, height[left]);
     
    
   

    

     

    
    

     

       left++;
     
    
   

    

     

    
    

     

       } else {
     
    
   

    

     

    
    

     
 if (minVal > height[right]) {
     
    
   

    

     

    
    

     

       res += minVal - height[right];
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       rightMax = Math.max(rightMax, height[right]);
     
    
   

    

     

    
    

     

       right--;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return res;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

时间空间表现并不好，和思路1差不多。

猜测是用Math.max()所以慢了。

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/103418095