42. 接雨水

ゝ一世哀愁。 2021-06-10 20:37 325阅读 0赞

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。  
![在这里插入图片描述][20191120123949273.png]  
上面是由数组 \[0,1,0,2,1,0,1,3,2,1,2,1\] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

> 输入: \[0,1,0,2,1,0,1,3,2,1,2,1\]  
> 输出: 6

每次找出最高的柱子和第二高的柱子，得出它们之间能容纳的雨水，然后通过递归得到左半部和右半部的结果相加就是所有的雨水了。

class Solution {
        public int trap(int[] height) {
            if(height==null || height.length == 0 || height.length == 1){
                return 0;
            }
            int start = 0;
            int end = height.length - 1;
            //去掉开头的0
            while(height[start] == 0){
                start++;
            }
            //去掉末尾的0
            while(height[end] == 0){
                end --;
            }
            if(start +1 >= end){
                return 0;
            }
            return recursion(arraySub(height,start,end));
        }
    
        public int recursion(int[] res){
            int total = 0;
            int start = 0;
            int end = res.length - 1;
            for(int i = 1; i<res.length -1;i++){
                //得到res中最高的两个柱子的坐标
                if(res[i] > res[start] || res[i] > res[end]){
                    if(res[start] > res[end]){
                        end = i;
                    }else{
                        start = i;
                    }
                }
            }
            //有可能出现end<start的情况
            if(start > end){
                int tmp = start;
                start = end;
                end = tmp;
            }
            //考虑两个柱子相邻的情况，就没必要计算了
            if(start + 1 != end){
            	//取两个柱子中较矮的那根
                if(res[start] > res[end]){
                    total = res[end] * (end - start - 1);
                }else{
                    total = res[start] * (end - start - 1);
                }
                //减去两根柱子之间的那些柱子的高度就是结果
                for(int i = start + 1;i < end;i++){
                    total -= res[i];
                }
            }
            //在start=1的情况下左子集必然只有两根柱子，所以不用考虑
            if(start > 1){
                //求左子集的雨水
                total += recursion(arraySub(res,0,start));
            }
            if(end < res.length-2){
                //求右子集的雨水
                int[] newRes = new int[res.length - end];
                System.arraycopy(res,end,newRes,0,newRes.length);
                total += recursion(newRes);
            }
            return total;
        }
    
        public static int[] arraySub(int[] data,int start,int end){
            int[] C=new int[end-start+1];//新建数组C长度为start-end
            for(int i=start,j=0;i<=end;i++,j++){
                C[j]=data[i];
            }
            return C;//返回截取数组的地址
        }
    
    }

[20191120123949273.png]: /images/20210606/275dac58540a44418fde5b341889087a.png