接雨水五解

接雨水

题目点这里

几何面积法 - 前后缀plus

雨水的高度 取决于 当前柱子左边最高柱 \(lmax\) 和右边最高柱 \(rmax\) 的最小值，这个最小值 ➖ 当前柱高度 就是此处雨水高度

用公式解释就是 $$Si = min(lmax, rmax) - Hi$$

想求 当前柱前缀最大值 和 后缀最大值，计算过程有点麻烦，但是我们可以不详细求出，因为上面式子求和以后就是 \(S = Sl和Sr重合面积 - Sh\) ，也就是 $$雨水面积 = 左边柱子投影面积 和 右边柱子投影面积 重合的地方 - 柱子面积$$ 只求出前缀最大值和后缀最大值的重合面积就可以，但是发现想求出这个重合面积有点麻烦，所以可以尝试 \(Sl + Sr - S矩\)，这个 \(S矩\) 就是长为 \(n\) 高为最高峰的矩形面积

所以公式变为 $$S = Sl + Sr - S矩 - Sh$$ 左投影 + 右投影 - 矩形 - 柱子

class Solution {
    public int trap(int[] height) {
        int lmax = 0, rmax = 0, s = 0;
        int n = height.length;
        for(int i = 0; i < n; i++) {
            lmax = Math.max(lmax, height[i]);
            rmax = Math.max(rmax, height[n - i - 1]);
            s += lmax + rmax - height[i];
        }
        return s - n * lmax;
    }
}

前后缀分解法

也就是上文提到的 求左投影和右投影重合的面积，需要分别求出每根柱子的前缀后缀最大值

class Solution {
    public int trap(int[] height) {
        int n = height.length, s = 0;
        int[] pre = new int[n];
        int[] suf = new int[n];
        pre[0] = height[0];
        suf[n - 1] = height[n - 1];
        for(int i = 1; i < n; i++) pre[i] = Math.max(pre[i - 1], height[i]);
        for(int i = n - 2; i >= 0; i--) suf[i] = Math.max(suf[i + 1], height[i]);
        for(int i = 0; i < n; i++) s += Math.min(pre[i], suf[i]) - height[i];
        return s;
    }
}

最高柱分解法

左投影和右投影的重合面积 --- 可以看作是 以最高柱为分界线，左边是左投影的面积，右边是右投影的面积，这两部分加起来就是重合面积

class Solution {
    public int trap(int[] height) {
        int s = 0, ma = 0, n = height.length, go = 0, lmax = 0, rmax = 0;
        for(int i = 0; i < n; i++) {
            if(height[i] > ma) {
                ma = height[i];
                go = i;
            }
        }
        for(int i = 0; i < go; i++) {
            lmax = Math.max(lmax, height[i]);
            s += lmax - height[i];
        }
        for(int i = n - 1; i > go; i--) {
            rmax = Math.max(rmax, height[i]);
            s += rmax - height[i];
        }
        return s;
    }
}

双指针

class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1, s = 0, lmax = 0, rmax = 0;
        while(l < r) {
            lmax = Math.max(lmax, height[l]);
            rmax = Math.max(rmax, height[r]);
            //左边的前缀和肯定没有后缀和大的时候，这里雨水就能确定了，l++
            if(lmax < rmax) {
                s += lmax - height[l];
                l++;
            }
            //右边后缀和一定没有前缀和大或者相等的时候
            else {
                s += rmax - height[r];
                r--;
            }
        } 
        return s;
    }
}

单调栈

class Solution {
    public int trap(int[] height) {
        Stack<Integer> st = new Stack<>();
        int s = 0;
        for(int i = 0; i < height.length; i++) {
            //遇到比栈顶大的，说明能够装雨水，栈顶就作为底层，出栈，新的栈顶和此时柱高的最小值和底层构成的矩形全是雨水
            while(!st.isEmpty() && height[st.peek()] <= height[i]) {
                int down = height[st.pop()];
                if(st.isEmpty()) break;
                int l = st.peek();
                int h = Math.min(height[l], height[i]) - down;
                s += h * (i - l - 1);
            }
            st.push(i);
        }
        return s;
    }
}