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

```public int Trap(int[] height) {
int res = 0;
int count =0;
foreach(var h in height) count+= h;

while(count>1)
{
int j =0;

while(height[j] == 0)
{
j++;
}
int trap = j;
int a = 0;
int minTrap = height[j];
for(int i =j+1;i< height.Count();i++)
{
if(height[i] !=0)
{
minTrap = Math.Min(minTrap,height[i]);
a += Math.Max(0,i-trap-1);
trap = i;
}
}
res += a*minTrap;
for(int i =0;i< height.Count();i++)
{
if(height[i]>0)
{
count-=minTrap;
height[i] -=minTrap;
}
}

}
return res;
}```

code如下：

```public int Trap(int[] height) {
int res = 0;
int size = height.Count();
var leftMax = new int[size];
var rightMax  = new int[size];

for(int i =1;i< size;i++)
{
leftMax[i] = Math.Max(height[i-1],leftMax[i-1]);
}
for(int i =size-2;i>=0;i--)
{
rightMax[i] = Math.Max(height[i+1], rightMax[i+1]);
}

for(int i =1;i< size-1;i++)
{
int min = Math.Min(leftMax[i],rightMax[i]);
if(height[i]<min)
{
res += min-height[i];
}
}

return res;
}```

```public int Trap(int[] height) {
int max =0;
int res = 0;
int size = height.Count();
if(size <= 2) return res;
int i =0;
var stack = new Stack<int>();//store the largerst heigth index
while(i< size)
{
if(stack.Count()==0 || height[i] <= height[stack.Peek()]) stack.Push(i++);
else
{
int bot = stack.Pop();
res += (stack.Count()==0)?0:((Math.Min(height[stack.Peek()], height[i]) - height[bot])*(i - stack.Peek()-1));;
}
}
return res;
}```

42. Trapping Rain Water

(0)
(0)