刷题不在多，而在精。

这道题号称字节的保洁阿姨都能做出的。

方法一：动态规划

下面这幅图简直封神，看了下图我才做出来的。

 两个方向遍历，然后取相同覆盖值-原始值（heigth数组）

这种方法更好理解。但是也有点难想出来。   可以想象吹风，被墙挡住了后面的沙子也和山那么高

从两头吹，然后能留下来的减去 里面坚硬的石头就是能装沙子的总容量了

 public static int trap(int[] height) {

        int []left=new int[height.length];
        int []right=new int[height.length];
        int left_max=0;
        int right_max=0;
        int n=height.length;
        for (int i = 0; i <n ; i++) {
            //从左向右遍历
            left_max=Math.max(height[i],left_max);
            left[i]=left_max;

            //从右向左
            right_max=Math.max(height[n-1-i],right_max);
            right[n-i-1]=right_max;

        }

        int result=0;
        for(int i=0;i<n;i++){
            int t=Math.min(left[i],right[i]);
            result+=t-height[i];
        }
        return result;
    }

方法二：双指针法

我对这种方法有点印象，但是还是忘了具体的做法。二刷之后茅塞顿开。

这种方法比方法一更难理解，但是更高效，时间复杂度来到了O(1)

维护两个指针 left 和 right，以及两个变量 leftMax 和 rightMax，初始时 left=0,right=n−1,leftMax=0,rightMax=0。指针 left 只会向右移动，指针 right 只会向左移动，在移动指针的过程中维护两个变量 leftMax 和 rightMax 的值。

当两个指针没有相遇时，进行如下操作：

使用 height[left] 和 height[right] 的值更新 leftMax 和 rightMax 的值；

如果 height[left]<height[right]，并且height[left]<leftMax，下标 left 处能接的雨水量等于 leftMax−height[left]，将下标 left 处能接的雨水量加到能接的雨水总量，然后将 left 加 1（即向右移动一位）；

如果 height[left]≥height[right]，并且height[right]<rightMax，下标 right 处能接的雨水量等于 rightMax−height[right]，将下标 right 处能接的雨水量加到能接的雨水总量，然后将 right 减 1（即向左移动一位）。

当两个指针相遇时，即可得到能接的雨水总量。

想象一下，你是左指针，右边的那位比你高，而你不是左边最高的，你后面还有大山，是不是一下雨你就一定能乘到水。即使你和你左边的一样高，那顶多乘水为0嘛。如果你比左边的还高的话，你这个位置就乘不到水了。

public static int trap(int[] height) {
        int left_max=0,right_max=0;
        int left=0,right=height.length-1;
        int result=0;//总共装水量
        while(left!=right){

            if(height[left]<height[right]){
                //如果左边小于右边，如果左边的值 <左最大值 证明可以装水
                if(height[left]<left_max){
                    result+=left_max-height[left];
                }else{
                    left_max=height[left];
                }
                left++;
            }else{
                //如果左边大于右边，如果右边的值 <右最大值 证明可以装水
                if(height[right]<right_max){
                    result+=right_max-height[right];
                }else{
                    right_max=height[right];
                }
                right--;
            }
        }
        return result;
    }