## 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;

}