这是LeetCode上面一道难度为困难的题目，实际解决起来并不困难，有多种实现方法，在此记录一下。
接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图如下：
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
左右查找解法（暴力法）：
private int trap(int[] height) {
// 定义结果
int res = 0;
// 数组长度
int len = height.length;
// 过滤掉最左边以及最右边那个柱子，不可能蓄水
for (int i = 1; i < len-1; i++) {
// 用于保存i位置左边以及右边的最大值
int left = 0,right = 0;
for (int j=i;j>=0;j--) {
left = Math.max(left,height[j]);
}
for (int j=i;j<len;j++) {
right = Math.max(right,height[j]);
}
// 取左右两边的最大值中，小的那个，计算出i位置储水量
res += Math.min(left,right)-height[i];
}
return res;
}
基于暴力法，通过保存左右遍历最大值，解法二：
private int trap(int[] height) {
// 返回值
int res = 0;
int len = height.length;
if (len<=1) return res;
// 保存i位置下左边的最大值
int[] left = new int[len];
// 保存i位置下右边的最大值
int[] right = new int[len];
// 初始化left为第一个值
left[0] = height[0];
// 遍历并保存i位置左侧最大值
for (int i=1;i<len;i++) {
left[i] = Math.max(height[i],left[i-1]);
}
// 初始化right为数组末端第一个值
right[len-1] = height[len-1];
// 遍历并保存i位置右侧最大值
for (int i=len-2;i>=0;i--) {
right[i] = Math.max(height[i],right[i+1]);
}
// 已知i位置左右最大值，比较得到小值并减去当前值，获取储水量
for (int i=1;i<len-1;i++) {
res+= Math.min(left[i],right[i])-height[i];
}
return res;
}
使用栈来存储坐标：
private int trap(int[] height) {
// 定义一个栈，用来保存下标
Stack<Integer> stack = new Stack<>();
int res = 0,cur = 0;
while (cur<height.length) {
// 如果栈不是空的，且当前高度大于栈顶高度
// 这时如果栈内存在比栈顶更高的元素，则行成蓄水结构
while (!stack.isEmpty() && height[cur]>height[stack.peek()]) {
// 弹出栈顶
int top = stack.pop();
if (stack.isEmpty()) {
break;
}
// 获取当前位置到栈顶位置的宽度
int distance = cur - stack.peek() - 1;
// 计算当前位置与栈顶位置的最小值，并获得与弹出条的高度差
int boundHeight = Math.min(height[cur],height[stack.peek()])-height[top];
// 乘积并累加
res += distance*boundHeight;
}
// 将当前坐标压入栈
stack.push(cur++);
}
// ex:[4,1,2,3]
// cur = 2 ， res += 1(2到4的距离)*1（2-1）
// cur = 3 ， res += 2(3到4的距离)*1（3-2）
return res;
}
双指针解法：
private int trap_3(int[] height) {
// 定义左右指针
int left = 0,right = height.length-1;
int res = 0;
// 用于保存左右最大值
int left_max = 0,right_max = 0;
// 结束条件
while (left<right) {
// 如果左指针高度小于右指针
if (height[left]<height[right]) {
// 如果左指针高度大于左最大高度，更新左最大高度
// 否则计算当前蓄水值
// 左指针右移一位
if (height[left]>=left_max) {
left_max=height[left];
} else {
res+=left_max-height[left];
}
left++;
} else {
// 左指针高度大于右指针时
// 右指针高度大于右最大高度，更新右最大高度
// 否则计算当前蓄水值
// 右指针左移一位
if (height[right]>=right_max) {
right_max = height[right];
} else {
res += right_max-height[right];
}
right--;
}
}
// ex:[4,1,2,3]
// => ex:[4(left,left_max),1,2,3(right,right_max)] 右指针小，右指针左移动一位
// => ex:[4(left,left_max),1,2(right,res+=3-2),3(right_max)] 右指针小，右指针左移动一位
// => ex:[4(left,left_max),1(right,res+=3-1),2,3(right_max)]
return res;
}
