Trapping Rain Water

题目地址：
https://leetcode.com/problems/trapping-rain-water/description/

题目：

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!

解题思路：
这道题就是用两个循环分别从左右两边开始扫，更新当前index可以储存的水量based on the max value from previous values。

代码：

public class TrappingRainWater {

    /*    *   Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.    *    leftMax = 3 (update if curr is larger or equals to leftMax)    *    rightMax = 3        *        *                               1        *               1               1   1       1        *   0   1   0   1   1   0   1   1   1   1   1   1        *   0   1   2   3   4   5   6   7   8   9   10  11    *    *  left:0   0   1   0   1   2   1   0   1   2   1   0    * right:0   2   3   1   2   3   2   0   0   1   0   0    * final:0   0   1   0   1   2   1   0   0   1   0   0    *    *  4, 2, 3    * */
    public int trap(int[] height) {
        if(height == null || height.length <= 2){
            return 0;
        }
        int len = height.length;
        int[] leftArray = new int[len];
        int[] rightArray = new int[len];
        int leftMax = height[0];
        int rightMax = height[len - 1];
        for(int i = 1; i <= len - 2; i++){
            if(height[i] >= leftMax){
                leftMax = height[i];
                leftArray[i] = 0;
            }
            else{
                leftArray[i] = leftMax - height[i];
            }
        }
        for(int i = len - 2; i >= 1; i--){
            if(height[i] >= rightMax){
                rightMax = height[i];
                rightArray[i] = 0;
            }
            else{
                rightArray[i] = rightMax - height[i];
            }
        }
        int rst = 0;
        for(int i = 1; i <= len - 2; i++){
            rst += Math.min(leftArray[i], rightArray[i]);
        }
        return rst;
    }

}