# [leetcode] Trapping Rain Water

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

```class Solution {
public:
int trap(int A[], int n) {
stack<int> s;
int lastLevel = 0;
int sum = 0;
int isIncreasing = true;
if(n <= 2){
return 0;
}
for(int i = 1; i < n ; i++){
if(A[i] >= A[i - 1] && s.empty() == true){//increasing
isIncreasing = true;
}
else if(A[i] < A[i - 1]){
if(isIncreasing == true){//i - 1 is the peek
s.push(i - 1);
}
s.push(i);
isIncreasing = false;
}
else{
while(s.empty() == false && A[s.top()] <= A[i]){
int left = s.top();
s.pop();
sum += (i - left - 1) * (A[left] - lastLevel);
lastLevel = A[left];
}
if(s.empty() == true){
lastLevel = 0;
isIncreasing = true;
}
else{
sum += (i - s.top() - 1) * (A[i] - lastLevel);
lastLevel = A[i];
s.push(i);
}
}
}
return sum;
}
};```

A[i]该柱子的存水量取决于它左边最高的柱子的值与右面最高柱子的值的最小值，即min(leftmost[i],rightmost[i]) – A[i]。所以可以这样来解：

```class Solution {
public:
int trap(int A[], int n) {
if(n < 3){
return 0;
}
int leftMost[n] = {0};
int rightMost[n] = {0};
int sum = 0;

leftMost[0] = A[0];
rightMost[n - 1] = A[n - 1];
for(int i = 1; i < n; i++){
leftMost[i] = max(leftMost[i - 1], A[i]);
rightMost[n - i - 1] = max(rightMost[n - i], A[n - i - 1]);
}
for(int i = 0; i < n; i++){
sum += abs(min(leftMost[i], rightMost[i]) - A[i]);
}
return sum;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.