class Solution {
    public int trap(int[] height) {
        if (height.length == 0) return 0;

        int sum = 0;
        Stack<Integer> stack = new Stack<>();
        // collect non-increasing heights
        for (int i = 0; i < height.length ;i++) {
            int h = height[i];
            if (stack.size() > 0) {
                Integer i_prev = stack.peek();
                int h_prev = height[i_prev];
                if (h > h_prev) {
                    // oh!oh! this is non-increasing anymore
                    sum += collect(height, stack, i);
                }
            }

            stack.push(i);
        }

        return sum;
    }

    public int collect(int[] height, Stack<Integer> stack, int i_right) {

        int sum = 0;
        int h_right = height[i_right];
        while (true) {
            if (stack.size() == 0) break;

            Integer i_now = stack.peek();
            int h_now = height[i_now];

            if (h_now > h_right) break;
            stack.pop(); // if pass, pop it out

            if (stack.size() == 0) break; // no left height anymore

            Integer i_left = stack.peek();
            int h_left = height[i_left];

            sum += (Math.min(h_left, h_right) - h_now) * (i_right - i_left - 1);

        }

        return sum;

    }

}