问题描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
例：输入: [0,1,0,2,1,0,1,3,2,1,2,1]；输出: 6
思路：
- 暴力法（按列求解）
- 栈
- 双指针
//java
//暴力法
class Solution {
public int trap(int[] height) {
int len = height.length;
if(len <= 2) return 0;
int maxleft, maxright;
int rain = 0;
for(int i = 0; i < len; ++i){
maxleft = maxright = 0;
for(int j = i; j >= 0; --j){//找到左边最大高度
maxleft = Math.max(maxleft, height[j]);
}
for(int j = i; j < len; ++j){//找到右边最大高度
maxright = Math.max(maxright, height[j]);
}
int cmax = Math.min(maxleft, maxright);
rain += (cmax > height[i]) ? cmax - height[i] : 0;//只有两边最小最大高度比当前列高，该列上才可能有水存在
}
return rain;
}
}
//暴力优化，空间换时间
class Solution {
public int trap(int[] height) {
int len = height.length;
if(len <= 2) return 0;
int maxleft, maxright;
int rain = 0;
int[] lefth = new int[len];//定义两个数组先把每个位置左右两边的最高高度保存下来
int[] righth = new int[len];
lefth[0] = height[0];
for(int i = 1; i < len; ++i){
lefth[i] = Math.max(lefth[i-1], height[i]);
}
righth[len-1] = height[len-1];
for(int i = len - 2; i >= 0; --i){
righth[i] = Math.max(righth[i+1], height[i]);
}
for(int i = 0; i < len; ++i){
int cmax = Math.min(lefth[i], righth[i]);
rain += (cmax > height[i]) ? cmax - height[i] : 0;
}
return rain;
}
}
//栈
class Solution {
public int trap(int[] height) {
int len = height.length;
if(len <= 2) return 0;
int rain = 0;
Stack<Integer> s = new Stack<>();
for(int index = 0; index < len; ++index){
while(!s.isEmpty() && height[s.peek()] < height[index]){//一旦遇到比自己大的元素，表明可能与前一个元素（比栈顶元素大）构成了水槽（相等时不构成）
int top = s.peek();
s.pop();
if(s.isEmpty()) break;
int d = index - s.peek() - 1;
rain += d * (Math.min(height[s.peek()], height[index]) - height[top]);//出栈元素上的水量
}
s.push(index);
}
return rain;
}
}
//双指针
class Solution {
public int trap(int[] height) {
int len = height.length;
if(len <= 2) return 0;
int left = 0;
int right = 1;
int rain = 0;
while(left < len && right < len){
if(height[right] >= height[left]){
rain += Math.min(height[left], height[right]) * (right - left - 1);
++left;
while(left < right){
rain -= height[left++];
}
}
++right;
}
right = len - 1;
int left1 = right - 1;
while(left < right){
if(height[left1] >= height[right]){
rain += Math.min(height[left1], height[right]) * (right - left1 - 1);
--right;
while(left1 < right){
rain -= height[right--];
}
}
--left1;
}
return rain;
}
}