7、双指针-接雨水

 按列求+辅助数组

1. 只关注每一列 当前能够留下几滴雨水。0和末尾位置不用考虑，盛不了雨水。
2. 现在 有个 0<i<length-1 位置，那么他能盛多少雨水呢？取决于左边最大值和右边最大值，Math.min(leftArr[i-1],rightArr[i+1])。再减去i位置的高度 就是可以盛的雨水，如果本身高度大于左右边最大值的最小值，那就是0。所以最终关系就是：Math.max(Math.min(leftArr[i-1],rightArr[i+1])-height[i],0)
3. 这里i不断递增情况下需要重新算左右边最大值问题。可以做两个辅助数组leftArr表示左边最大值数组，rightArr表示右边最大值数组。

代码如下：

class Solution {
    public int trap(int[] height) {
        if (height==null||height.length<2){
            return 0;
        }
        int N=height.length;
        //建立辅助数组
        int[] leftArr=new int[N];
        int[] rightArr = new int[N];
        leftArr[0]=height[0];
        for (int i = 1; i < N; i++) {
            leftArr[i]=Math.max(leftArr[i-1],height[i]);
        }
        rightArr[N-1]=height[N-1];
        for (int i = N-2; i>=0; i--) {
            rightArr[i]= Math.max(height[i], rightArr[i + 1]);
        }
        int S=0;
        for (int i = 1; i < N-1; i++) {
            S+=Math.max(Math.min(leftArr[i-1],rightArr[i+1])-height[i],0);
        }
        return S;
    }
}

双指针

1. 首先 0和length-1 位置不用计算，无法盛水。
2. 现在L指针到1 R指针到length-2, lMax表示左侧最大值，rMax表示右侧最大值。
3. 如果lMax<=rMax：说明 L左侧最大值是lMax，右侧最大值不知道，但是肯定是不小于rMax。并且有lMax<=rMax，漏桶效应，以左侧最大值为准，那就说明L位置可以结算了。
4. 反之 右侧结算

代码如下：

class Solution {
    public int trap(int[] height) {
       if (height==null||height.length<2){
            return 0;
        }
        int N=height.length;
        int L=1;
        int R=N-2;
        int lMax=height[0];
        int rMax=height[N-1];
        int s=0;
        while (L<=R){
            if (lMax<=rMax){
                s+=Math.max(lMax-height[L],0);
                lMax=Math.max(lMax,height[L]);
                L++;
            }else {
                s+=Math.max(rMax-height[R],0);
                rMax=Math.max(rMax,height[R]);
                R--;
            }
        }
        return s;
    }
}