给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
image
本题可以将每个长度为1的空隙所能积累的雨水加起来，所得结果即为答案。每个这样的空隙的储水量由其左右两侧的柱子高度决定，为1（宽度）*左右两侧最高的柱子中较矮的一个的高度，如此我们用两个数组存储左右两侧最高的数组，再进行遍历叠加即可。
public int trap(int[] height){
if(height.length<3)
return 0;
int[] leftmax=new int[height.length];
int[] rightmax=new int[height.length];
int ans=0;
leftmax[0]=height[0];
rightmax[height.length-1]=height[height.length-1];
for(int i=1;i<height.length;i++){
leftmax[i]=Math.max(leftmax[i-1],height[i]);
}
for(int i=height.length-2;i>=0;i--){
rightmax[i]=Math.max(rightmax[i+1],height[i]);
}
for(int i=1;i<height.length-1;i++){
int temp=Math.min(leftmax[i-1],rightmax[i+1])-height[i];
if(temp>0)
ans+=temp;
}
return ans;
}
