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!

This problem turned out to be easier than I thought. I was trying to use the same approach as the Largest Rectangle in Histogram, that was not correct and was too complicated.

The idea is as simple as, what you would normally think: the water can only be trapped between two bars that are higher than the current one.
So, we first calculated the bar that has the maximum height left to the current one. Then we iterate from the end of the array and calculate the right-maximum-height bar.
In the mean time, we can calculate the trapped water by taking the minimum between left-maximum and right maximum, and then deducting the current bar's height.

public class TrapRain {
    public int trap(int[] A) {
        if (A == null || A.length <= 2)
            return 0;
        int[] left_max_height = new int[A.length];
        left_max_height[0] = A[0];
        int left_maxh = A[0];
        for (int i = 1; i < A.length; i++)
        {
            left_maxh = Math.max(left_max_height[i - 1], A[i]);
        }
        
        int total = 0;
        int right_maxh = A[A.length - 1];
        for (int i = A.length - 2; i > 0; i--)
        {
            right_maxh = Math.max(A[i], right_maxh);
            int container = Math.min(left_max_height[i], right_maxh);
            if (container > A[i])
                total += container - A[i];
            right_maxh = Math.max(right_maxh, A[i]);
        }
        return total;
    }
}