题目链接
https://leetcode-cn.com/problems/trapping-rain-water/文章源自随机的未知-https://sjdwz.com/11134.html
题目内容
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6文章源自随机的未知-https://sjdwz.com/11134.html
思路
我们可以设置两个数组，left_height_array和right_height_array;
其中left_height_array表示当前柱子前面的所有柱子的最高值（不包括当前柱子）；
right_height_array表示当前柱子后面的所有柱子的最高值（不包括当前柱子）；
取left_height_array[i]与right_height_array[i]两个值的最小值，如果相等则取这个相同的值，存储在res数组中
在height[i]处可以存的水量的求法：
如果res[i]的值比height[i]大，当前凹处可以存res[i] - height[i]的水;
如果res[i]的值不比height[i]大，不能存水；
再把res[i]累加便可以得到最终存水量。
（其实可以在比较left_height_array[i] 与 right_height_array[i] 大小关系时就可以进行累加存水量了。）文章源自随机的未知-https://sjdwz.com/11134.html
案例分析
height : [0,1,0,2,1,0,1,3,2,1,2,1]
先求解 left_height_array[i] 从前往后算：
第一个元素左边没有元素，所以left_height_array[0] = 0；
第二个元素左边元素有0，左边最高的是0，所以left_height_array[1] = 0;
第三个元素左边元素有0，1，左边最高的是1，所以left_height_array[2] = 1;
第四个元素左边元素有0，1，0，左边最高的是1，所以left_height_array[3] = 1;
第五个元素左边元素有0，1，0，2，左边最高的是2，所以left_height_array[4] = 2;
第六个元素左边元素有0，1，0，2，1左边最高的是2，所以left_height_array[5] = 2;
第七个元素左边元素有0，1，0，2，1，0，左边最高的是2，所以left_height_array[6] = 2;
第八个元素左边元素有0，1，0，2，1，0，1左边最高的是2，所以left_height_array[7] = 2;
第九个元素左边元素有0，1，0，2，1，0，1，3左边最高的是3，所以left_height_array[8] = 3;
第十个元素左边元素有0，1，0，2，1，0，1，3，2左边最高的是3，所以left_height_array[9] = 3;
第十一个元素左边元素有0，1，0，2，1，0，1，3，2，1左边最高的是3，所以left_height_array[10] = 3;
第十二个元素左边元素有0，1，0，2，1，0，1，3，2，1，2左边最高的是3，所以left_height_array[11] = 3;文章源自随机的未知-https://sjdwz.com/11134.html
所以left_height_array数组为
0，0，1，1，2，2，2，2，3，3，3，3
同理可求得right_height_array数组为
3，3，3，3，3，3，3，2，2，2，1，0；
height数组为：
0，1，0，2，1，0，1，3，2，1，2，1
index=0时，left_height_array[0] = 0,right_height_array[0] = 0不能放水，存水量为0；
index=1时，left_height_array[1] = 0,right_height_array[1] = 3不能放水，两者最小为0，存水量为0；
index=2时，left_height_array[2] = 1,right_height_array[1] = 3不能放水，两者最小为2，而height[i]为0，存水量为两者最小值 - height[i] = 1；
以此类推；
最后把它们都相加即可。文章源自随机的未知-https://sjdwz.com/11134.html
代码
class Solution {
public int trap(int[] height) {
int result = 0;
if(height.length == 0) return result;
int[] left_height_array = new int[height.length];
int[] right_height_array = new int[height.length];
int left_max = 0;
int right_max = 0;
left_height_array[0] = 0;
right_height_array[0] = 0;
for(int i = 1;i<height.length;i++){
if(height[i-1]>left_max){
left_max = height[i-1];
}
left_height_array[i] = left_max;
}
for(int i = height.length -2;i>=0;i--){
if(height[i+1]>right_max){
right_max = height[i+1];
}
right_height_array[i] = right_max;
}
for(int i=0;i<height.length;i++){
if(left_height_array[i] == right_height_array[i]){
if(left_height_array[i] > height[i])
result+=left_height_array[i]-height[i];
}else if(left_height_array[i] < right_height_array[i]){
if(left_height_array[i] > height[i])
result+=left_height_array[i]-height[i];
}else{
if(right_height_array[i]>height[i])
result += right_height_array[i] - height[i];
}
}
return result;
}
}
欢迎关注
扫下方二维码即可关注,微信公众号:随机的未知
文章源自随机的未知-https://sjdwz.com/11134.html
