Trapping Rain Water

给一个数组, 里面的数字代表bar的高度, 求这些bar能圈住多少面积水. 这个题其实很难, 不是看答案真不会.

public class Solution {
    public int trap(int[] height) {
        if(height.length == 0 || height == null)
            return 0;
        int max = 0;
        int maxIndex = -1;
        for(int i = 0 ; i < height.length; i++){
            if(height[i] > max){
                max = height[i];
                maxIndex = i;
            }
        }
        
        int pre  = 0;
        int sum = 0;
        for(int i = 0; i < maxIndex ; i++) {
            if(height[i] > pre){
                sum += (height[i] - pre) * (maxIndex - i);
                pre = height[i];
            }
            sum -= height[i];
        }
        pre = 0;
        for(int i = height.length - 1; i > maxIndex; i--) {
            if(height[i] > pre){
                sum += (height[i]-pre) * (i - maxIndex);
                pre = height[i];
            }
            sum -= height[i];
        }
        return sum;
    }
}