/* 扫描确定边界
1, 木桶能状多少水取决与最短的木板, 所以找到 h = min(左边最高, 右边最高) - curH, 
2. 宽度为1, 累加高度即可
*/

/** 单调栈
1. 从右向左做投影来看, 每个柱子能拦截到多少水由它左边第一个比它高的柱子决定
2. 如果y柱子是在x柱子左边且第一个比x高的柱子, x能蓄积的水量就是 x~y之间每个柱子z[i]与x的高度差乘上z[i]与x的距离
3. 使用单调栈找每个柱子左边第一个比它高的柱子, 中间弹出的值就z[i], 逐步累加即可
4. 还要加上y 和 x 之间的段落差产生的水柱, (h[x] - last) * (y-x-1)
*/

class Solution {
    public int trap(int[] height) {
        // return bounds(height);
        return monoStack(height);
    }

    public int monoStack(int[] height){
        Stack<Integer> stack = new Stack<>();
        int n = height.length;
        int count = 0;
        for (int i = 0 ; i < n ; i++){
            int last = 0;
            while(!stack.isEmpty() && height[stack.peek()] < height[i]){
                int w = i-stack.peek()-1;
                int h = height[stack.peek()] - last;
                count += w*h;
                last = height[stack.pop()];
            }
            if (!stack.isEmpty()) count += (height[i] - last) * (i - stack.peek() - 1);
            stack.push(i);
        }
        return count;
    }

    public int bounds(int[] height){

        if (height == null || height.length == 0) return 0;
        int n = height.length;
        int[] left = new int[n];
        int[] right = new int[n];

        left[0] = height[0];
        for (int i = 1 ; i < n ; i++){
            left[i] = Math.max(left[i-1], height[i]);
        }

        right[n-1] = height[n-1];
        for (int i = n-2 ; i >= 0; i--){
            right[i] = Math.max(right[i+1], height[i]);
        }

        int res = 0;
        for (int i = 0 ; i < n ; i++){
            res += Math.min(left[i], right[i]) - height[i];
        }
        return res;        
    }
}