Sharing my java solution using stack


  • 1
    P
    public class Solution {
    public int trap(int[] height) {
        if(height.length == 0)
            return 0;
        Stack<Integer> stack = new Stack<Integer>(); // store index, min stack of height[i]
        int vol = 0;
        for(int i = 0; i < height.length; i++) {
            int cur = height[i];
            if(stack.empty() || height[stack.peek()] > cur) {
                stack.push(i);
            } else {
                while(!stack.empty() && height[stack.peek()] < cur) {
                    int index = stack.pop();
                    if(!stack.empty()) {
                        int j = stack.peek();
                        int edge = Math.min(cur, height[j]);
                        vol += (i - j - 1) * (edge - height[index]);
                    }
                }
                stack.push(i);
            }
        }
        return vol;
    }
    

    }


  • 0

    I think the expression height[stack.peek()] < cur
    should be modified to height[stack.peek()] <= cur.
    Anyway this might be not important, just a minor issue.


Log in to reply
 

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