Trapping Rain Water

Source

• leetcode: 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.

Java

public class Solution {
    public int trap(int[] height) {
        int result=0;
        int n = height.length;
        //find min on left
        int[] left = new int[n];
        for(int i=1; i<n; i++){
            left[i] = Math.max(height[i-1], left[i-1]);
        }

        //find min on right
        int[] right = new int[n];
        for(int i=n-2; i>=0; i--){
            right[i] = Math.max(height[i+1], right[i+1]);
        }

        for(int i=0; i<n; i++){
            int min = Math.min(left[i], right[i]);
            if(min-height[i]>0){
                result+=min-height[i];
            }
        }
        return result;
    }
}