Java using Stack, with explanation


  • 2
    J

    Credit to @jiaohy https://discuss.leetcode.com/topic/47181/sharing-my-java-solution-using-stack
    Added in-line comments and change variable name for better understanding

    public class Solution {
        public int trap(int[] height) {
            if(height.length == 0) return 0;
            Stack<Integer> stack = new Stack<Integer>(); // store index
            int vol = 0;
            for(int i = 0; i < height.length; i++) {
                // columns in stack will be decreasing in height.
                // current column index is "i"
                if(stack.empty() || height[stack.peek()] >= height[i]) stack.push(i);
                // if we encounter a column lower  than the previous one, push it to stack.
                else {
                // if we encounter a column higher than the previous one (denoted as "mid"), start poping,
                // calculate the water trapped between column before mid(denote as "j") and "i"
                    while(!stack.empty() && height[stack.peek()] < height[i]) {
                        int mid = stack.pop();
                        if(!stack.empty()) {
                            int j = stack.peek();
                            vol += (i - j - 1) * (Math.min(height[i], height[j]) - height[mid]);
                        }
                    }
                    stack.push(i);
                }
            }
            return vol;
        }
    }
    

Log in to reply
 

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