思路：接雨水在面试中很常见，有三种解法。分别是暴力解法、双指针优化和单调栈。
一、暴力解法：暴力解法也是使用双指针（超时）。
1.明确按照行来算还是列来算。
（1）按照行来算：
（2）按照列来算：
2.以按照列来算为例（因为按照列来算更容易理解）。
（1）如果按照列来算，宽度一定为1，再把每一列雨水的高度求出来即可。
（2）每一列雨水的高度，取决于该列左侧最高的柱子和右侧的最高的柱子中最矮的那个柱子的高度。以求列4的雨水高度为例，如下图所示。
——列4的左侧最高的柱子为列3，高度为2（以下用lHeight表示）。
——列4的右侧最高的柱子为列7，高度为3（以下用rHeight表示）。
——列4柱子的高度为1（以下用height表示）。
——那么列4的雨水高度为：列3和列7的高度最小值，再减去列4的高度，即min(lHeight,rHeight) - height。
——列4的雨水高度求出来了，宽度为1，相乘就是列4的雨水体积了。
（3）只要从头遍历一遍所有的列，然后求出每一列雨水的体积，相加之后就是总雨水的体积了（注意第一个柱子和最后一个柱子不接雨水）。
附代码：
class Solution { public int trap(int[] height) { int sum = 0; for(int i = 0;i < height.length;i++){ //第一个柱子和最后一个柱子不接雨水 if(i == 0 || i == height.length - 1){ continue; } int lHeight = height[i]; //记录左边柱子的最高高度 int rHeight = height[i]; //记录右边柱子的最高高度 for(int l = i - 1;l >= 0;l--){ if(height[l] > lHeight){ lHeight = height[l]; } } for(int r = i + 1;r < height.length;r++){ if(height[r] > rHeight){ rHeight = height[r]; } } int h = Math.min(lHeight,rHeight) - height[i]; if(h > 0){ sum += h; } } return sum; } }二、双指针优化。
1.在暴力解法中，是有重复计算的，这是因为为了得到两边的最高高度，使用了双指针来遍历，每到一个柱子都向两边遍历一遍。
2.优化：把每一个位置的左边最高高度记录在一个数组上（maxLeft），右边最高高度记录在一个数组上（maxRight），以避免重复计算。
3.思路：在当前位置，左边的最高高度是前一个位置的左边的最高高度和本高度的最大值；右边的最高高度也同理。
（1）从左向右遍历：maxLeft[i] = max(height[i]，maxLeft[i - 1])。
（2）从右向左遍历：maxRight[i] = max(height[i]，maxRight[i + 1])。
附代码：
（一）双指针：
class Solution { public int trap(int[] height) { int len = height.length; if(len <= 2){ return 0; } int[] maxLeft = new int[len]; int[] maxRight = new int[len]; //记录每个柱子左边柱子的最大高度 maxLeft[0] = height[0]; for(int i = 1;i < len;i++){ maxLeft[i] = Math.max(height[i],maxLeft[i - 1]); } //记录每个柱子右边柱子的最大高度 maxRight[len - 1] = height[len - 1]; for(int i = len - 2;i >= 0;i--){ maxRight[i] = Math.max(height[i],maxRight[i + 1]); } //求和 int sum = 0; for(int i = 0;i < len;i++){ int count = Math.min(maxLeft[i],maxRight[i]) - height[i]; if(count > 0){ sum += count; } } return sum; } }（二）双指针优化版。
class Solution { public int trap(int[] height) { if(height.length <= 2){ return 0; } //从两边向中间寻找最值 int maxLeft = height[0],maxRight = height[height.length - 1]; int l = 1,r = height.length - 2; int res = 0; while(l <= r){ //不确定上一轮是左边移动还是右边移
