leetcode17.21

解题思路

• 主要思路就是分治法，观察柱状图可以看出海拔较高处的雨水量与比他低的地方的高度无关，所以就可以先把最高处的雨水量算出来，再解决剩下柱状图中的高处雨水量...
• 虽然代码写的比较多，但好在容易理解，时间复杂度也是O(n)

代码

class Solution {
    public int trap(int[] height) {
        if(height.length<3)
        return 0;
        return def(height,0,height.length-1);
    }
    public int def(int[] nums,int s,int e){
        if(s==e||s==e-1)
        return 0;
        int maxindex=s,max=nums[s];
        int lmax=s,second1=nums[s];
        int rmax=e,second2=nums[e];
        for(int i=s;i<e;++i){
            if(nums[i]>max){
                second1=max;
                max=nums[i];
                lmax=maxindex;
                maxindex=i;
            }
        }
        if(max==0)
        return 0;
        for(int i=e;i>maxindex;--i){
            if(nums[i] > second2){
                second2 = nums[i];
                rmax = i;
            }
        }
        
        return def(nums,s,lmax)+count(nums,lmax,maxindex)+count(nums,maxindex,rmax)+def(nums,rmax,e);
    }
    public int count(int[] nums,int s,int e){
        if(s==e||s==e-1)
        return 0;
        int c=0;
        int m=Math.min(nums[s],nums[e]);
        for(++s;s<e;++s){
            if(m>nums[s]){
                c+=(m-nums[s]);
            }
        }
        return c;
    }
}