# LeetCode: Trapping Rain Water

By | 2012 年 10 月 31 日

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.

## Notes

• `3.times{|i| p i}`, prints `0,1,2`

## Solutions

### Ruby

```# @param {Integer[]} height
# @return {Integer}
def trap(height)
# record the left heights
lefts = []
left = 0
height.each do |h|
lefts.push left
left = h if left < h
end
# record the right heights
rights = []
right = 0
height.size.times do |i|
h = height[-i-1]
rights.unshift(right)
right = h if right < h
end
# calculate trapped
trapped = 0
lefts.each_with_index do |left, idx|
right = rights[idx]
h = height[idx]
potential = [left, right].min - h
trapped += potential if potential > 0
end
trapped
end
```

### C++, 44ms过大集合

```class Solution {
public:
int trap(int A[], int n) {
//no way to contain any water
if(n <= 2) return 0;

//1. first run to calculate the heiest bar on the left of each bar
int *lmh = new int[n];//for the most height on the left
lmh[0] = 0;
int maxh = A[0];
for(int i = 1; i < n; ++i) {
lmh[i] = maxh;
if(maxh < A[i]) maxh = A[i];
}
int trapped = 0;

//2. second run from right to left,
// caculate the highest bar on the right of each bar
// and calculate the trapped water simutaniously
maxh = A[n-1];
for(int i = n - 2; i > 0; --i) {
int left = lmh[i];
int right = maxh;
int container = min(left,right);
if(container > A[i]) {
trapped += container - A[i];
}
if(maxh < A[i]) maxh = A[i];
}
delete lmh;
return trapped;
}
};
```

## 3 thoughts on “LeetCode: Trapping Rain Water”

1. Hong Jiang
```var Q =  [0,1,0,2,1,0,0,1,3,2,1,2,1];

function Trapping(Q) {
var i = 0;
var j = Q.length-1;
var water = 0;

while (i<j) {
if (Q[i] Q[i+1]) {
water = water + (Q[i]-Q[i+1]);
Q[i+1] = Q[i];
}
i++;
} else {
if (Q[j-1] < Q[j]) {
water = water + (Q[j]-Q[j-1]);
Q[j-1] = Q[j];
}
j--;
}
}

console.log(water);
}

Trapping(Q);
```
2. 12344
```class Solution {
public:
int trap(int A[], int n) {
if(n==0) return 0;
int l = 0, r = n-1,block = 0,all = 0,curlevel = 0;
while(lcurlevel)
{
all += (min(A[l],A[r])-curlevel)*(r-l+1);
curlevel = min(A[l],A[r]);
}
if(A[l]<A[r])
block += A[l++];
else
block += A[r--];
}
return all-block;
}
};
```