接雨水

经典面试算法

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

单调栈

思路：维护一个单调栈：当加入的元素大于栈顶，则依次弹出较小的元素 每次需要弹出元素的时候，开始计算存水量：高：Math.min(height[i],height[stack.peek()])-height[stack.pop] 宽：(i-stack.peek()-1)

public int trap(int[] height) {
        if(height == null){
            return 0;
        }
        // 单调栈
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        for (int i = 0; i < height.length; i++) {
            // 满足条件
            while (!stack.empty()&&height[stack.peek()]<height[i]){
                // 出栈
                int pop = stack.pop();
                if(stack.empty()){
                    break;
                }
                // 计算
                res += (i-stack.peek()-1)*(Math.min(height[i],height[stack.peek()])-height[pop]);
            }
            stack.push(i);
        }
        return res;
    }
复制代码

几何知识

1. 利用左右指针的下标差值计算出每一行雨水+柱子的体积，如图第一行体积为11，第二行为8，第三行为1。累加得到整体体积tmp=20tmp=20（每一层从左边第一个方格到右边最后一个方格之间一定是被蓝黑两种颜色的方格填满的，不会存在空白，这也是为什么能按层求的关键）
2. 计算柱子体积，为height：[0,1,0,2,1,0,1,3,2,1,2,1]height：[0,1,0,2,1,0,1,3,2,1,2,1] 数组之和SUM=14SUM=14（也可以直接用sum()函数，不过时间复杂度就是O(2n)了）
3. 返回结果 tmp-SUMtmp−SUM就是雨水的体积

public int trap(int[] height) {
        int len = height.length;
        int left = 0,right = len-1;
        int sum = 0,tep = 0,high = 1;
        while (left<=right){
            while (left<=right&&height[left]<high){
                sum +=height[left];
                left++;
            }
            while(left<=right&&height[right]<high){
                sum+=height[right];
                right--;
            }
            high++;
            tep += right-left+1;
        }
        return tep-sum;
    }
复制代码