（大厂笔试题）Java两种方法解决蓄水池问题

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

栈的选取问题
class Solution {
public int trap(int[] height) {
Stack st = new Stack<>();//一个栈
int current=0;//当前下表
int sum=0;//总的数字之和
while(current<height.length) {
while(!st.isEmpty()&&height[current]>height[st.peek()]){//当前的高度大于栈内的高度
int h = height[st.peek()];//选取栈内的高度
st.pop();//出栈
if(st.isEmpty()){
break;
}
int distance=current-st.peek()-1;//槽内的距离
int min=Math.min(height[st.peek()],height[current]);//判断两峰之间哪一个更低
sum+=distance(min-h);//求取值高
}
st.push(current);//不满足条件进栈
current++;
}
return sum;
}
}*

双指针求解
class Solution {
public int trap(int[] height) {
//双指针求值
int left_max=0,right_max=0;
int left=0,right=height.length-1;
int sum=0;
while(left<right){
if(height[left]<height[right]){
if(height[left]>left_max){left_max=height[left];}//如果大于此时最大值重新赋值
else{
sum+=left_max-height[left]；//或者把当前两个值相减得到当前峰值
}
left++;
}
else{
if(height[right]>right_max){right_max=height[right];}
else{
sum+=right_max-height[right];
}
right–;
}
}
return sum;
}
}