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!

Solution1: 

public class Solution {
    public int trap(int[] A) {
        if(A == null || A.length == 0)
            return 0;
        
        int result = 0;
        int[] left = new int[A.length];   //left数组记录到当前i为止，左边最高的bar(包含i)
        int[] right = new int[A.length];   //right数组记录到当前i为止，右边最高的bar
        
        left[0] = A[0];
        for(int i = 1; i < A.length; i++) {
            left[i] = Math.max(left[i - 1], A[i]);
        }
        
        right[A.length - 1] = A[A.length - 1];
        for(int i = A.length - 2; i >= 0; i--) {
            right[i] = Math.max(right[i + 1], A[i]);
        }
        
        for(int i = 0; i < A.length; i++) {  
            //第i块地方的存水量 = min(第i块左边最高的bar高度, 第i块右边最高的bar的高度) - 第i块地方bar的高度
            result += Math.min(left[i], right[i]) - A[i];
        }
        return result;
    }
}

Solution2:

这种方法是基于动态规划的，基本思路就是维护一个长度为n的数组，进行两次扫描，一次从左往右，一次从右往左。第一次扫描的时候维护对于每一个bar左边最大的高度是多少，存入数组对应元素中，第二次扫描的时候维护右边最大的高度。这个方法只需要两次扫描，所以时间复杂度是O(2*n)=O(n)。空间上需要一个长度为n的数组，空间复杂度是O(n)。

public class Solution {
    public int trap(int[] A) {
        if(A == null || A.length == 0)
            return 0;
        
        int result = 0;
        int max = 0;
        int[] container = new int[A.length];
        
        for(int i = 0; i < A.length; i++) {
            container[i] = max;
            max = Math.max(max, A[i]);
        }
        
        max = 0;
        for(int i = A.length - 1; i >= 0; i--) {
            container[i] = Math.min(container[i], max);
            max = Math.max(max, A[i]);
            if(container[i] - A[i] > 0)
                result += container[i] - A[i];
            else
                result += 0;
        }
        
        return result;
    }
}

Solution3:

只需要一次扫描就能完成。基本思路是这样的，用两个指针从两端往中间扫，在当前窗口下，如果哪一侧的高度是小的，那么从这里开始继续扫，如果比它还小的，肯定装水的瓶颈就是它了，可以把装水量加入结果，如果遇到比它大的，立即停止，重新判断左右窗口的大小情况，重复上面的步骤。这里能作为停下来判断的窗口，说明肯定比前面的大了，所以目前肯定装不了水（不然前面会直接扫过去）。这样当左右窗口相遇时，就可以结束了，因为每个元素的装水量都已经记录过了。这个算法每个元素只被访问一次，所以时间复杂度是O(n)，并且常数是1，比前面的方法更优一些。

public class Solution {
    public int trap(int[] A) {
        if(A == null || A.length == 0)
            return 0;
        
        int result = 0;
        int l = 0, r = A.length - 1;
        
        while(l < r) {
            int min = Math.min(A[l], A[r]);
            if(A[l] == min) {
                l++;
                while(l < r && A[l] < min) {
                    result += min - A[l];
                    l++;
                }
            }else {
                r--;
                while(l < r && A[r] < min) {
                    result += min - A[r];
                    r--;
                }
            }
        }
        return result;
    }
}