/**
* 接雨水
* LeetCode42.
* 给出一排宽度为1、高度为n的柱子，求可以接到雨水的面积
* 示例：height = {1,0,2,1,3,1,0,1,2,0,1} 输出：7
* 使用动态规划的方式去接此题
* */
public int rain(int[] nums){
int size = nums.length;
//定义两个数组，用来记录当前位置的左侧最大值/右侧最大值
int[] maxLeft =new int[size];//左侧最大值
int[] maxRight =new int[size];//右侧最大值
maxLeft[0] = nums[0];//初始化
maxRight[size-1] = nums[size-1];
//填充左侧最大值，当前左侧最大值=当前值与前一位左侧最大值的max
for (int i=1; i
maxLeft[i] = Math.max(nums[i], maxLeft[i-1]);
}
//填充右侧最大值，当前右侧最大值=当前值与后一位右侧最大值的max
for (int i=size-2; i>=0;i--){
maxRight[i] = Math.max(nums[i], maxRight[i+1]);
}
System.out.println(Arrays.toString(maxLeft));
System.out.println(Arrays.toString(maxRight));
int area =0;
//计算雨水面积
//雨水面积 = 当前位置左右侧最小值-当前位置值
for (int i=0;i
area += Math.min(maxLeft[i], maxRight[i]) - nums[i];
}
return area;
}
