接雨水

问题陈述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

如图，可接下6个单位的雨水。

思路分析

利用单调栈，单调栈就是永远保证栈内元素单调递增或递减。

代码实现

class Solution{
    public int trap(int[] height){
        if(height==null){
            return 0;
        }
        Stack<Integer> stack=new Stack<>();
        int ans=0;
        for(int i=0;i<height.length;i++){
            //当栈不空，判断当前指向height[i]是否大于上一个已入栈元素的高
            while(!stack.isEmpty()&&height[stack.peek()]<height[i]){
                int curIdx=stack.pop();
                //如果栈顶元素一直相等，那么一直pop出去，只留下第一个。
                while(!stack.isEmpty()&&height[stack.peek()]==height[curIdx]){
                    stack.pop();
                }
                if(!stack.isEmpty()){
                    int stackTop=stack.peek();
                    // stackTop此时指向的是此次接住的雨水的左边界的位置。右边界是当前的柱体，即i。
                    // Math.min(height[stackTop], height[i]) 是左右柱子高度的min，减去height[curIdx]就是雨水的高度。
                    // i - stackTop - 1 是雨水的宽度。
                    ans += (Math.min(height[stackTop], height[i]) - height[curIdx]) * (i - stackTop - 1);

                }
            }
            stack.add(i);//单调栈添加元素在此
        }
        return ans;
    }
}