Trapping Rain Water

Given?n?non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,?
Given?[0,1,0,2,1,0,1,3,2,1,2,1], return?6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.?Thanks Marcos?for contributing this image!

?

public class Solution {
    public int trap(int[] height) {
    	return solve(height, 0, height.length-1);
    }
	private int solve(int[] height, int start, int end) {
		if ((start+1) >= end) {
			return 0;
		}
        int maxIndex = -1;
        int secondMaxIndex = -1;
        for (int i = start; i <= end; i++) {
        	if (secondMaxIndex==-1 || height[i]>height[secondMaxIndex]) {
        		secondMaxIndex = i;
        		if (maxIndex==-1 || height[secondMaxIndex]>height[maxIndex]) {
        			int t = secondMaxIndex;
        			secondMaxIndex = maxIndex;
        			maxIndex = t;
        		}
        	}
        }
        int left = Math.min(secondMaxIndex, maxIndex);
        int right = Math.max(secondMaxIndex, maxIndex);
        int leftpart = solve(height, start, left);
        int rightpart = solve(height, right, end);
        int res = 0;
        for (int i = left+1; i < right; i++) {
        	res += height[secondMaxIndex]-height[i];
        }
        return leftpart+res+rightpart;
	}
}

?

Trapping Rain Water

原文：http://hcx2013.iteye.com/blog/2218805