Concise Java Solution use Stack


  • 2
    S

    Each time I come across a bar, pop all previous bar that is no greater than it as well as sum up water trapped. And then, when the peek bar of stack is greater than it, calculate water trapped against that bar.

    public class Solution {
        public int trap(int[] A) {
            Stack<Integer> stack = new Stack<Integer>();
            int sum = 0;
            int pre = 0;
            int i = -1;
            while(++i < A.length){
                if(A[i]==0){pre = 0;continue;}
                while(!stack.isEmpty() && A[i] >= A[stack.peek()]){
                    sum += (A[stack.peek()] - pre) * (i-stack.peek()-1);
                    pre = A[stack.pop()];
                }
                if(!stack.isEmpty()){
                    sum += (A[i] - pre) * (i-stack.peek()-1);
                    pre = A[i];
                }
                stack.push(i);
            }
            return sum;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.