wayetan
12/31/2013 - 2:17 AM

## Trapping Rain Water

Trapping Rain Water

``````public class Solution{
public int trap(int[] A) {
// skip zeros
int cur = 0;
while (cur < A.length && A[cur] == 0)
++cur;

// check each one
int vol = 0;
Stack<Integer> stack = new Stack<Integer>();
while (cur < A.length) {
while (!stack.isEmpty() && A[cur] >= A[stack.peek()]) {
int b = stack.pop();
if (stack.isEmpty())
break;
vol += ((cur - stack.peek() - 1) * (Math.min(A[cur], A[stack.peek()]) - A[b]));
}
stack.push(cur);
++cur;
}

return vol;
}
}``````
``````/**
* 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.
*/
public class Solution {
public int trap(int[] A) {
int res = 0;
if(A.length < 2)
return res;
int[] leftMost = new int[A.length];
int[] rightMost = new int[A.length];
// Initialization;
leftMost[0] = 0;
rightMost[A.length - 1] = 0;
for(int i = 1; i < A.length - 1; i++){
leftMost[i] = Math.max(leftMost[i - 1], A[i - 1]);
}
for(int i = A.length - 2; i >= 0; i--){
rightMost[i] = Math.max(rightMost[i + 1], A[i + 1]);
}
for(int i = 0; i < A.length; i++){
if(Math.min(leftMost[i], rightMost[i]) - A[i] > 0){
res += Math.min(leftMost[i], rightMost[i]) - A[i];
}
}
return res;
}
}``````