[数据结构与算法]LeetCode 42题

LeetCode 42题

class Solution {
    public int trap(int[] height) {
        if(null == height || height.length < 3) {
            return 0;
        }
        int len = height.length;
        int result = 0;
        int left = 0;
        int right = 0;
        for(int i = 0; i < len; i++) {
            if(0 == i && height[0] < height[1]) {
                continue;
            }
            left = height[i];
			for(int j = i+1; j < len; j++) {             
                right = height[j];

                if(len - 1 != j && left > right) {
                    if(len - 1 != j && left > right) {
                    if(height[j-1] <= height[j] && j+1 < len && height[j] >= height[j+1]) {
                        boolean flag = false;
                        for(int temp = j; temp < len; temp++) {
                            if(height[temp] > right) {
                                flag = true;
                                break;
                            }
                        }
                        //flag为false，后面没有比此数要大的数了
                        if(!flag) {
                            result += calcu(height, i, j);
                            i += j-i-1;
                            break;
                        }else {
                            continue;
                        }
                    }
                continue;
                }

                }
                if(j == len - 1 && height[j-1] > height[j]) {
                    int temp = j-1;
                    for(int k = j-2; k > i; k--) {
                        if(height[k] < height[k+1]) {
                            temp = k+1;
                            break;
                        }
                    }
                    result += calcu(height, i, temp);
                    i += j-i-1;
                    break;
					}else {
                    result += calcu(height, i, j);
                    i += j-i-1;
                    break;
                }
            }
        }
        return result;
    }
    private int calcu(int[] arr, int left, int right) {
        int flag = 0;
        int sum = 0;
        if(arr[left] > arr[right]) {
            flag = arr[right];
        }else {
            flag = arr[left];
        }
        for(int i = left+1; i < right; i++) {
            if(arr[i] < flag) {
                sum += flag - arr[i]; 
            }
        }
        return sum;
    }	
}