思路一：相向双指针
这里为什么用到双指针？我们可以通过题目来看一下，因为我们需要装水，所以需要一种形状为“凹”类似的容器来装水。这样的话，我们需要讨论的无非就是两边的容器壁大小了。
如果你想着用相同方向的双指针进行遍历，有几种特殊情况你需要进行细分的讨论：当遍历到最后的时候高度依然小于左边的时候（当然假设我们以左边的容器壁为主）我们不得不进行讨论刚刚已经遍历过的容器壁是否能够装水，这样的话还需要再次移动左边指针再遍历一次，会增加时间复杂度，很麻烦。
这里就是一种新思路，相向，也就是把左指针放到最左边，右指针放到最右边，然后进行判断。除了这样，我们需要维护最左边的最高容器壁，和最右边的最高容器壁。因为如果我们移动指针，这个时候一边容器壁反而降低了，这样就不可能能够接到水（如果遇到凹坑，也就是高度为0），所以我们两边都需要维护这个容器壁高度。为什么又说是最高呢？我们遍历其实就是按照容器壁从小到大高度时一共能够盛多少水的，其实就是一步一步增高，一个一个判断水的容量，这样不仅清晰，而且能够不重不漏的计算出来水容量。（是不是有点动态规划转移状态那个味道呢？）
假设我们左边的容器壁当前并没有右边的容器壁高，那么我们这个时候需要看一看中间是否能够构成凹形。如果能，我们计入水容量（通过左边的最大容器壁-当前左指针指向的容器壁高度），不能，我们看看是不是跟当前最大容器壁的高度更大，更大就更新，否则不然。换做是右边也是一样的。
class Solution {public int trap(int[] height) {int left=0;int right=height.length-1;int leftMax=height[left];int rightMax=height[right];int res=0;while(left<=right){if(leftMax<rightMax){res+=leftMax-height[left];left++;if(left<=height.length-1){leftMax=Math.max(leftMax,height[left]);}}else{res+=rightMax-height[right];right--;if(right>=0){rightMax=Math.max(rightMax,height[right]);}}}return res;}
}思路二：单调栈
其实一开始并不知道为什么能够用这个方法进行解答。经过上一个方法的思路提取，我们知道一个根本的东西：就是我们一直在两边维护着最高的容器壁这一点。对于没有最高容器壁高度的部分，我们选择竖向计算水的容量。这里就不同于上一种方法了，我们这时开始横向的计算水容量，维护容器壁的高度也用单调栈维护。
这里用了非递增的单调栈，当我们遇见比栈顶高的容器壁的时候，就出栈然后计算当前横向的水容量，直到遇见栈内比它大的容器壁为止，不然就一直退栈计算容量，一直到栈为空的时候或者遍历完全部高度。
注意：我们在计算高度的时候是需要先出栈，获得出栈元素，然后再提取出来当前栈顶元素和当前比出栈元素大的高度，比较这两个高度谁小。为什么？因为可能这个元素比刚刚出栈的元素对应的容器壁高度大，但是不一定比后面的栈元素对应的容器壁的高度大，所以需要额外判断一下。至于横向的长度怎么算，直接用当前的元素坐标-栈内存储的栈顶元素就行。（栈内维护的是数组的坐标值）。
class Solution {public int trap(int[] height) {Deque<Integer>stack=new LinkedList();int res=0;for(int i=0;i<height.length;i++){while(!stack.isEmpty()&&height[stack.peek()]<height[i]){int num=stack.pop();if(stack.isEmpty())break;res+=(Math.min(height[stack.peek()],height[i])-height[num])*(i-stack.peek()-1);}stack.push(i);}return res;}
}