给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图 ，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
共三种解法
下面是三种解法的思想，以及代码（带有详细注释）
解法一 动态规划法找到每一列左边和右边（包括本身）的最高的一列，比较左右两边，取其较小值，这个值就是可以承接雨水的高度，注意在这里并不考虑本身有多高，因为我们在计算左右两边最高值的时候已经带着本身的高度，得出的最小值减去本身的高度就是这一列要填充的雨水
代码如下：
var trap = function(height) {
let ans=0;
let leftMax=[];//每一列左边的最大值
let rightMax=[];//右边
let lM=-Infinity;//左边最大值
let rM=-Infinity;
//第一步先确定左边的最大值
for(let i=0;ilM)
lM=height[i];
leftMax[i]=lM;
}
//确定右边时要注意从最右边开始
for(let i=height.length-1;i>=0;i--){
if(height[i]>rM)rM=height[i];
rightMax[i]=rM;
}
//第二步开始比较左右两边并确定每一列的雨水
for(let i=0;i
解法二 单调栈法
使用一个栈来记录递减的下标，
当下一个元素等于栈顶下标对应的元素时，将栈顶元素取出放入；
当前下标小于时，直接将当前下标入栈；
大于时，进行循环，将栈顶下标取出，如果此时栈内还有元素，则说明还有比该列更大的，所以就计算该列左边与右边的较小的值（同解法一的思路），但是由于是单调递减栈！故当前栈顶的元素下标就是左边最小值，与当前的进行比较，取较小值再减去该列的高度，就是要填补的高度h，宽度就是此时栈顶元素下标与i的差值减一得到w，h*w。循环直至栈顶元素不小于i位置或者栈为空
var trap = function(height) {
let ans=0;
let st=[0];
for(let i=1;iheight[st[st.length-1]]){
let temp=st[st.length-1];
st.pop();
if(st.length){
let w=i-st[st.length-1]-1;
let h=Math.min(height[i],height[st[st.length-1]])-height[temp]
ans+=w*h;
}
}
st.push(i);
}
}
return ans;
};
解法三 双指针法
属于方法一的简化版；
明确每一列的雨水数目是与其左边的最大值或者右边最大值相关的，且是由两值中的最小值决定的，那么我们就用双指针从数组两边遍历，当左边最大值小于右边最大值时，只需要关心左边这一部分即可，那么左指针就推进一步，反之同理。当然左右两边最大值是随时更新的。
var trap = function(height) {
let ans=0;
//左右最大值
let lM=0;
let rM=0;
//左右指针
let left=0;
let right=height.length-1;
while(left<=right){
if(lMlM){
lM=height[left]
}else{
ans+=lM-height[left];
}
left++;
}
else{
if(height[right]>rM){
rM=height[right];
}else{
ans+=rM-height[right];
}
right--;
}
}
return ans;
};
