Java with Stack, following the approach similar to Largest Rectangle in Histogram


  • 9
    X
    public class Solution {
        public int trap(int[] height) {
            int len = height.length;
            int water = 0;
            Stack<Integer> stack = new Stack<>();
            for(int i = 0; i < len; i++) {
                if (stack.isEmpty() || height[stack.peek()] >= height[i]) {
                    stack.push(i);
                } else {
                    int tmp = stack.pop();
                    if (!stack.isEmpty()) {
                        water += (Math.min(height[stack.peek()],height[i])-height[tmp])*(i-stack.peek()-1);
                    }
                    i--;
                }
            }
            return water;
        }
    }

  • 1

    Great solution, easy to understand!


Log in to reply
 

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