[Leetcode] Trapping Rain Water

Trapping Rain WaterMar 10 '124164/10550
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
この問題は前に面接で似たようなものに出会ったことがある.
しかし2次元の場合、当時は混乱していた.それからネット上で良い方法を見ました:境界から、境界の上で最も低い板を取って中へfloodfillとして、高い停止に遭遇します.
この問題は似たような処理で,ずっと簡単だ.
2 D:http://www.cnblogs.com/liangfeng/archive/2011/09/19/2181695.html

class Solution {
public:
    int trap(int A[], int n) {
        int i = 0, j = n - 1, res = 0, cur;
        int *a = A;
        while (i < j) {
            if (a[i] < a[j]) {
                cur = i+1;
                while (cur <= j && a[cur] <= a[i]) res += a[i] - a[cur++];
                i = cur;
            } else {
                cur = j - 1;
                while (cur >= i && a[cur] <= a[j]) res += a[j] - a[cur--];
                j = cur;
            }
        }
        return res;
    }
};