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.

Have you met this question in a real interview? 

Yes

Example

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

Challenge

O(n) time and O(1) memory

O(n) time and O(n) memory is also acceptable.

public class Solution {
    /**
     * @param heights: an array of integers
     * @return: a integer
     */
    public int trapRainWater(int[] heights) {
        // write your code here
        if(heights == null || heights.length == 0) return 0;
        int maxIndex = 0;
        int preMax = 0;
        int count = 0;
        for(int i = 0; i < heights.length; i++){
            maxIndex = heights[i] > heights[maxIndex] ? i : maxIndex;
        }
        for(int i = 0; i < maxIndex; i++){
            if(heights[preMax] > heights[i]){
                count += (heights[preMax] - heights[i]);
            } else preMax = i;
        }
        preMax = heights.length-1;
        for(int i = heights.length-1; i > maxIndex; i--){
            if(heights[preMax] > heights[i]){
                count += (heights[preMax] - heights[i]);
            } else preMax = i;
        }
        return  count;
    }
}