Trapping Rain Water 363

Question

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.

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.

Solution

前后指针法，时间复杂度O(n)，空间复杂度O(1)。

1) 前指针指向数组头，后指针指向数组尾。

2) 比较前后指针，从小的那个开始（记录此时最初指针的值smaller），

3) 向后或前移动指针，当遇到小于等于它的元素(index为i)时，新增加的面积为smaller-heights[i]，当遇到大于它的元素时停止.重复2-3步骤，直到前后指针交叠。

此处要说明的是，在第2步移动的必须是较小值的指针，这就好比一根短木板和一根长木板，若以长木板为基准向短木板推进，水会漏出，反之则可以。

代码如下：

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 start = 0;
        int end = heights.length - 1;
        int area = 0;
        while(start < end){
            if(heights[start] < heights[end]){
                int smaller = heights[start];
                while(start < end && heights[start] <= smaller){
                    area += smaller - heights[start];
                    start++;
                }
            }else{
                int smaller = heights[end];
                while(start < end && heights[end] <= smaller){
                    area += smaller - heights[end];
                    end--;
                }
            }
        }
        return area;
    }
}