接雨水

接雨水

class Solution {
    public int trap(int[] height) {
        int res = 0;
        Deque<Integer> heightDeque = new ArrayDeque<>();

        for(int i = 0;i < height.length;i++){
            while(!heightDeque.isEmpty()&&height[i] > height[heightDeque.peek()]){
                int lower = heightDeque.pop();
                //只有一个，删完重新新增边界
                if(heightDeque.isEmpty()){
                    break;
                }
                //有间隙，计算雨水，只计算有长度差的，其他的挪出，下次计算会清除掉
                int length = i - heightDeque.peek() - 1;
                res += length * (Math.min(height[i],height[heightDeque.peek()])-height[lower]);
            }
            heightDeque.push(i);
        }
        return res;
    }
}