42 接雨水
算出两边的最高位置的最小值 减去当前位置的高度就是当前位置的蓄水量
public int trap(int[] height) {
//边的总个数
int n = height.length;
//从左到右的height[]的最大值
int [] leftsum = new int[n];
//从右到左的height[]的最大值
int [] rightsum =new int[n];
//先计算从左到右的大值
leftsum[0] = height[0];
for (int i = 1; i < n; i++) {
leftsum[i] = Math.max(leftsum[i-1], height[i]);
}
//计算从右到左的最大值
rightsum[n-1] = height[n-1];
for (int i = n-2; i >= 0; i--) {
rightsum[i] = Math.max(rightsum[i+1], height[i]);
}
//最终存水结果
int target=0;
//选出两个中的最小值减去当前位置的高度 就是当前位置所能存储水的多少
for (int i = 0; i < n; i++) {
target+=Math.min(leftsum[i],rightsum[i])-height[i];
}
return target;