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 trap…

leetcode_trapping_rain_water.cpp

#define MAXN 100000
int _left[MAXN];
int _right[MAXN];

class Solution {
public:
    int trap(int A[], int n) {
        for (int i = 0; i < n; ++i) {
            if (i == 0)
                _left[i] = A[i];
            else
                _left[i] = max(A[i], _left[i - 1]);
        }
        for (int i = n - 1; i >= 0; --i) {
            if (i == n - 1)
                _right[i] = A[i];
            else
                _right[i] = max(A[i], _right[i + 1]);
        }
        int ret = 0;
        for (int i = 1; i < n - 1; ++i) {
            int diff = min(_left[i - 1], _right[i + 1]) - A[i];
            ret += diff > 0 ? diff : 0;
        }
        return ret;
    }
};