刷题不在多，而在精。

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

方法一：动态规划

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

 两个方向遍历，然后取相同覆盖值-原始值（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;}