Trapping Rain Water

 基本思路是这样的，用两个指针从两端往中间扫，在当前窗口下，如果哪一侧的高度是小的，那么从这里开始继续扫，如果比它还小的，肯定装水的瓶颈就是它了， 可以把装水量加入结果，如果遇到比它大的，立即停止，重新判断左右窗口的大小情况，重复上面的步骤。这里能作为停下来判断的窗口，说明肯定比前面的大了， 所以目前肯定装不了水（不然前面会直接扫过去）。这样当左右窗口相遇时，就可以结束了，因为每个元素的装水量都已经记录过了。代码如下：
int trap(int A[], int n) {
    int i = 0, j = n-1;
    int volume = 0;       
    int k = 0;
    while (i < j) {
        if (A[i] <= A[j]) {
            k = i+1;
            while (A[i] > A[k]) {
                volume += (A[i]-A[k]);
                k++;
            }
            i = k;
        }
        else {
            k = j-1;
            while (A[j] > A[k]) {
                volume += (A[j]-A[k]);
                k--;
            }
            j = k;
        }
    }  
    return volume;       
}


//method 2, by anniekim.
DP solution: Find left bound and right bound for each element. O(n).

int trap(int A[], int n) {
    if (n == 0) return 0;
    vector<int> maxLeft(n,0);
    vector<int> maxRight(n,0);
    maxLeft[0] = A[0];
    maxRight[n - 1] = A[n - 1];
    for (int i = 1; i < n; ++i) {
        maxLeft[i] = max(maxLeft[i - 1], A[i]);
        maxRight[n - 1 - i] = max(maxRight[n - i], A[n - 1 - i]);
    }
    int res = 0;
    for (int i = 1; i < n; ++i) {
        res += min(maxLeft[i], maxRight[i]) - A[i];
    }
    return res;
}