接雨水
题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [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
思路
经典dp题，以前有一题是求能用多大的矩形覆盖，一样的思路
定义两个左右数组打表，记录当前高度最多能放多少水，需要从左往右找左边最高的（不算自己），从右往左找右边最高的也不算自己
处理完后，只要枚举一遍求和即可
Java实现
public int trap(int[] height) {
if(height.length<3)
return 0;
int ans=0;
int[] right = new int[height.length+1],left = new int[height.length+1];
left[height.length-1]=0;
right[0]=0;
for(int i=1;i<height.length;i++)
left[i] = Math.max(left[i-1],height[i-1]);
for(int i=height.length-2;i>=0;i--)
right[i] = Math.max(right[i+1],height[i+1]);
for(int i=0;i<height.length;i++){
int min_height = Math.min(left[i],right[i]);
if (height[i]<min_height){
ans+=(min_height-height[i]);
}
}
return ans;
}
执行用时 :1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗 :37.9 MB, 在所有 Java 提交中击败了80.80%的用户
