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`

.

**Solution** ** 1**: Use stack to do it, scan the array, if we found that the current value is >= max in the stack, calculate how much water it is able to trap. otherwise, add to stack.

[0,1,0,2,1,0,1,3,2,1,2,1]

0 add

stack : 0

1 add (greater than max = 0 in stack, calculate result)

stack: 1 result = (max – 0)

0 add

stack: 1, 0

2 add (greater than max = 1 in stack, calculate result)

stack: 2 result = (max – 0) + (max – 1)

1, 0, 1 add

stack: 2, 1, 0, 1

3 add (greater than max = 2 in stack, calculate result)

stack: 3 result = (max – 1) + (max – 0) + (max – 1) + (max – 2)

….

See code for more detailed information.

public int Trap(int[] A)
{
var res = 0;
var stack = new Stack();
var max = 0;
for (int i = 0; i < A.Length; i++)
{
while (stack.Any() && A[i] >= max)
{
var top = stack.Pop();
res += max - A[top];
}
stack.Push(i);
max = Math.Max(max, A[i]);
}
var curMax = stack.Any() ? A[stack.Peek()] : 0;
while (stack.Any())
{
var top = stack.Pop();
if (curMax <= A[top])
{
curMax = A[top];
}
else
{
res += curMax - A[top];
}
}
return res;
}

**Solution 2:** do not use stack. using two pointers to solve it. find max value and its index, move left pointer from 0 to max index, right pointer from len – 1 to max index. so every time, we know how much water it can trap.

public int Trap2(int[] height)
{
var res = 0;
var max = 0;
var maxindex = -1;
for (int i = 0; i < height.Length; i++)
{
if (height[i] > max)
{
max = height[i];
maxindex = i;
}
}
var leftmax = 0;
for (int i = 0; i < maxindex; i++)
{
leftmax = Math.Max(leftmax, height[i]);
res += leftmax - height[i];
}
var rightmax = 0;
for (int i = height.Length - 1; i >= maxindex; i--)
{
rightmax = Math.Max(rightmax, height[i]);
res += rightmax - height[i];
}
return res;
}

**Solution 3**: more concise solution for solution 2. we do not need to find the max value index.

public int Trap3(int[] height)
{
var res = 0;
var max = 0;
var left = 0;
var right = height.Length - 1;
while (left <= right)
{
if (height[left] < height[right])
{
max = Math.Max(max, height[left]);
res += max - height[left];
left++;
}
else
{
max = Math.Max(max, height[right]);
res += max - height[right];
right--;
}
}
return res;
}