1.问题描述
给定 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
2.方法
直观想法
直接按问题描述进行。对于数组中的每个元素，我们找出下雨后水能达到的最高位置，等于两边最大高度的较小值减去当前高度的值。
3.执行代码
class Solution {
public int trap(int[] height) {
int ans=0;
for(int i=1;i<height.length-1;i++){
int left_max=0,right_max=0;
for(int j=i;j>=0;j--){
left_max=max(left_max,height[j]);//向左遍历找最大值
}
for(int j=i;j<=height.length-1;j++){
right_max=max(right_max,height[j]);//向右遍历找最大值
}
ans+=min(left_max,right_max)-height[i];//遍历到当前元素所接雨水总数
}
return ans;
}
private int max(int a, int b ) {
if(a>b) return a;
else return b;
}
private int min(int a, int b) {
if(a<b) return a;
else return b;
}
}
4.复杂度分析
时间复杂度： O(n2)。数组中的每个元素都需要向左向右扫描。
空间复杂度 O(1)的额外空间。
