Trapping Rain Water

一维向内灌水 两个指针即可

code

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 l = 0;
        int r = heights.size()-1;

        int sum = 0;

        while(l != r)
        {
            if(heights[l] > heights[r])
            {
                int pivot = heights[r];
                r--;
                while(l != r && heights[r] < pivot)
                {
                    sum += pivot-heights[r];
                    r--;
                }
            }
            else
            {
                int pivot = heights[l];
                l++;
                while(l != r && heights[l] < pivot)
                {
                    sum += pivot-heights[l];
                    l++;
                }
            }
        }

        return sum;
    }
};