leetcode(42)接雨水

接雨水

解题思路：分冶法+递归

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        if(len<=2){
            return 0;
        }
        return trap(height,0,len);
    }
    public int trap(int[] height,int start,int end){
        if(end-start<=2){
            return 0;
        }
        int max = maxv(height,start,end);
        int max2 = maxv(height,start,max);
        int max3 = maxv(height,max+1,end);
        int trap2 = trap(height,start,max2+1);
        int trap3 = trap(height,max3,end);
        int temp = 0;
        int sum = 0;
        temp = height[max2];
        for(int i=max2+1;i<max;i++){
            sum += temp-height[i];
        }
        if(max3<end){
            temp = height[max3];
        }
        for(int i=max+1;i<max3;i++){
            sum += temp-height[i];
        }
        return sum + trap2+trap3;
    }
    public int maxv(int[] height,int start,int end){
        int max = start;
        for(int i=start+1;i<end;i++){
            if(height[i]>height[max]){
                max = i;
            }
        }
        return max;
    } 
}