leetcode 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.

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!

For each bar i, the value of rain equals to :

min(left_top, right_top) – (bar i value)

left_ top is the bar with top-most height  and in the left of bar i, and right_top is the bar with top-most height and in the right of bar i.

In order to obtain left_top and right_top, maintain two arrays, one stores the left_top for each bar, and one stores the right_top for each bar.

For a particular bar i, if the A[i] is larger than left_top[i – 1], then left_top[i] equals to A[i]. Otherwise left_top[i] equals to left_top[i – 1]. the array right_top[i] is totally the same principle as left_top array.

int trap(int A[], int n) {
vector<int> left(n, 0);
vector<int> right(n, 0);

for (int i = 0; i < n; i++) {
left[i] = A[i];
right[i] = A[i];
}

for (int i = 1; i < n; i++) {
if (A[i] > left[i – 1]) {
left[i] = A[i];
} else {
left[i] = left[i – 1];
}
}

for (int i = n – 2; i >= 0; i–) {
if (A[i] > right[i + 1]) {
right[i] = A[i];
} else {
right[i] = right[i + 1];
}
}

int ret = 0;
for (int i = 0; i < n; i++) {
ret += (min(left[i], right[i]) – A[i]);
}

return ret;
}