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.

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

分析：

接雨水问题的解决方法如下：

1. 找到左边和右边的墙有多高
2. 从更低的一端开始，
    如果当前的格子比上一个格子低，就加水
    如果当前的格子比上一个格子高，就更新墙
3. 一直做到两个指针碰撞

重点是，当start = end的时候，还需要计算一次，因为有可能这个格子也需要加水。

解法：

class Solution {
public:
    /**
     * @param heights: a vector of integers
     * @return: a integer
     */
    int trapRainWater(vector<int> &heights) {
        // write your code here
        if (heights.size() == 0) {
            return 0;
        }
        int start = 0;
        int end = heights.size() - 1;
        int startHeight = heights[start];
        int endHeight = heights[end];
        int water = 0;
        while (start <= end) {
            if (startHeight < endHeight) {
                if (heights[start] < startHeight) {
                    water += startHeight - heights[start];
                } else if (heights[start] > startHeight) {
                    startHeight = heights[start];
                }
                start++;
            } else {
                if (heights[end] < endHeight) {
                    water += endHeight - heights[end];
                } else if (heights[end] > endHeight) {
                    endHeight = heights[end];
                }
                end--;
            }
        }
        return water;
    }
};