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;
    }
}