力扣第42题接雨水

这个为什么要单独写一篇文章，一方面是因为这个题我写了四个题解，另一方面是我觉得这题挺有意思的值得单独写一篇文章。

原题

题解一：

我自己的想法，算是双指针变体实现吧。本来是要用左右指针来实现的，结果写着写着就跑偏了，但是最后这个代码性能还是不错的可以看看。

class Solution {
    public int trap(int[] height) {
        int size = 0;
        int left = 0;
        for (int i = 1; i < height.length; i++) {
            if (height[left] <= height[i]) {
                int min = height[left];
                left++;
                while (left < i) {
                    size += min - height[left];
                    left++;
                }
            }
        }
        int a = height.length - 1;
        for (int i = height.length - 2; i >= left; i--) {
            if (height[i] >= height[a]) {
                int min = height[a];
                a--;
                while (a > i) {
                    size += min - height[a];
                    a--;
                }
            }
        }
        return size;
    }
}

题解二：

动态规划,这个是我觉得比较巧妙的一个解法

class Solution {
    public int trap(int[] height) {
        //从左往右看的最大值
        int[] leftMax = new int[height.length];
        //从右往左看的最大值
        int[] rightMax = new int[height.length];

        leftMax[0]=height[0];
        for (int i = 1; i < height.length; i++) {
            if(height[i]>leftMax[i-1]) leftMax[i]=height[i];
            else leftMax[i]=leftMax[i-1];
        }
        
        rightMax[rightMax.length-1]=height[height.length-1];
        for (int i = rightMax.length-2; i >= 0; i--) {
            if(height[i]>rightMax[i+1]) rightMax[i]=height[i];
            else rightMax[i]=rightMax[i+1];
        }
        
        //记录可以接多少雨水
        int size=0;
        for (int i = 0; i < height.length; i++) {
            size+=Math.min(leftMax[i],rightMax[i])-height[i];
        }
        return size;
    }
}

题解三：

单调栈

class Solution {
    public int trap(int[] height) {
        int size=0;
        Stack<Integer> stack=new Stack<>();
        for (int i = 0; i < height.length; i++) {
            if(!stack.empty()&&height[stack.peek()]<=height[i]){
                int last=stack.peek();
                while(!stack.empty()){
                    int top=stack.peek();
                    size+=(Math.min(height[i],height[top])-height[last])*(i-top-1);
                    if(height[top]>height[i]) break;
                    else last=stack.pop();
                }
            }
            stack.push(i);
        }
        return size;
    }
}

题解四：

双指针

class Solution {
    public int trap(int[] height) {
        int size = 0;
        int left = 0;
        for (int i = 1; i < height.length; i++) {
            if (height[left] <= height[i]) {
                int min = height[left];
                left++;
                while (left < i) {
                    size += min - height[left];
                    left++;
                }
            }
        }
        int a = height.length - 1;
        for (int i = height.length - 2; i >= left; i--) {
            if (height[i] >= height[a]) {
                int min = height[a];
                a--;
                while (a > i) {
                    size += min - height[a];
                    a--;
                }
            }
        }
        return size;
    }
}

具体的细节，以后再补充