11 Container With Most Water 42.Trapping Rain Water

11 和 42 本质上都是木桶原理:  

 11 如何才能存最多的水? 

假设 a[left] < a[right] ,    total = a[left] *(right-left) ,  那么 right -1, right-2 位置 都比 total 小, 此时就没必要move right 了, 因为所有的right -x 都比 right 小。

此时只需要move left 指针, 继续找最大value. 

11 Container With Most Water  42.Trapping Rain Water

 code 很简单: 

    public int maxArea(int[] height) {
          
        int start = 0;
        int end = height.length-1;
        int max = 0;
      
        while(start< end) {
          if(height[start] < height[end]) {
              max = Math.max(max,(height[start]*(end-start)));
              start ++;
          }  
          
          else  {
              max = Math.max(max,height[end]*(end-start));
              end --;
          } 
        }   
        return max;      
    }

 

 

42 题 

11 Container With Most Water  42.Trapping Rain Water

 

随便一个 ai ,如果存在某个left 点   ai-left > ai  并且存在 right 点  ai-right >ai , 则 ai 的水可以存的住, 无论 left  是否是 i 的邻居, 隔着很远也能决定ai 能被存下来。   那能存多少呢? 存多少 取决于 ai-left or ai-right 的最小值, 这就是木桶原理。

那么从left 到right 扫描一遍, 找到每个点left 的max value ,存数组 leftMax[]    并且  从right  ->left 找每个点往right 看的max value.  存到一个数组里 rightMax[]

然后  能存住的水 就是 min(leftMax[i], rightMax[i]) - a[i]

code 也很简单:

    public int trap(int[] height) {
        
        if(height == null || height.length<3) return 0;
        
        int n = height.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        
        leftMax[0] = height[0];
        for(int i=1; i<n ; i++){
            leftMax[i] = Math.max(leftMax[i-1],height[i]);
        }
        
        rightMax[n-1] = height[n-1];
        for(int i = n-2; i>=0; i--){
            rightMax[i] = Math.max(rightMax[i+1],height[i]);
        }
        
        int ans = 0;
        
        for(int i=0; i<n; i++){
            ans += Math.min(leftMax[i],rightMax[i]) - height[i];
        }
        
        return ans;
    

时间 复杂度为 O(N) 空间复杂度也是 O(n) ,但实际并不用额外的空间。 用two point 方法,木桶原理, 维护一个 leftMax 以及 rightMax ,如果leftMax < rightMax , 只用move leftMax 就行了,然后 ans += Math.min(leftMax,rightMax) - height[i]. 

    public int trap(int[] height) {
       if(height == null || height.length <3) return 0; 
        
       int n = height.length; 
       int leftBound = 0;
       int rightBound = 0;
        
       int left = 0;
       int right = n-1;
       int ans = 0 ;
        
       while(left<right){
           leftBound = Math.max(height[left],leftBound);
           rightBound = Math.max(height[right],rightBound);
           
           if(leftBound < rightBound){
              ans += leftBound - height[left];
              left++;    
           }
           
           else {
               ans += rightBound - height[right];
               right--;
           } 
       }
        
       return ans; 
    }

 

407. Trapping Rain Water II

把42题的平面变成立体,方法完全变了。得用BFS来做, 可参考 https://www.cnblogs.com/grandyang/p/5928987.html

11 Container With Most Water 42.Trapping Rain Water

上一篇:【iOS】Swift4.0 GCD的使用笔记


下一篇:快速安装create-react-app脚手架