【LeetCode】Trapping Rain Water

浏览数：24 / 时间：2015年06月11日

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!

双指针i,j分别从首尾开始扫，记当前i指针遇到的最大值为leftWall，j指针遇到的最大值为rightWall

（1）leftWall <= rightWall

对于i指针指向的位置，被trap的值为(leftWall-A[i])。

i前进一个位置。

解释如下：

a.如果i与j之间不存在比leftWall大的值，那么i位置trap的值就取决与leftWall与rightWall的较小值，也就是leftWall

b.如果i与j之间存在比leftWall大的值，其中离leftWall最近的记为newLeftWall，那么i位置trap的值就取决与leftWall与newLeftWall的较小值，也就是leftWall

（2）leftWall > rightWall

对于j指针指向的位置，被trap的值为(rightWall-A[j])。

j前进一个位置。

解释同上。

class Solution {
public:
    int trap(int A[], int n) {
        if(n < 3)   //at least 3 integers
            return 0;
        
        int i = 0;
        int j = n-1;
        int leftWall = 0;
        int rightWall = 0;
        int ret = 0;
        while(i <= j)
        {
            //update leftWall and rightWall
            leftWall = max(leftWall, A[i]);
            rightWall = max(rightWall, A[j]);
            if(leftWall <= rightWall)
            {//no matter whether there is a more higher wall between leftWall and rightWall
             //A[i] is dependent on leftWall if leftWall <= rightWall
                ret += (leftWall-A[i]);
                i ++;
            }
            else
            {//no matter whether there is a more higher wall between leftWall and rightWall
             //A[j] is dependent on rightWall if rightWall < leftWall
                ret += (rightWall-A[j]);
                j --;
            }
        }
        return ret;
    }
};