接雨水

题目需求:给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
输入:height = [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 个单位的雨水(蓝色部分表示雨水)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public int trap(int[] height) {
int x=height.length; //定义int,接纳高度
if(x==0)//该处做个判断,如果高度为0,就不用继续了
{
return 0;//没有就返回0
}
int[] leftmax=new int[x];//设置一个左遍历的数组
leftmax[0]=height[0];//设置初始值
for(int i=1;i<x;++i)//从下标i开始,与前一项比对
{
leftmax[i]=Math.max(leftmax[i-1],height[i]);//记录下谁高,两两比较,最大的挪出来
}
int[] rightmax=new int[x];//设置一个右遍历的数组
rightmax[x-1]=height[x-1];//从倒数第二个开始
for(int i=x-2;i>=0;--i)
{
rightmax[i]=Math.max(rightmax[i+1],height[i]);//第一次与倒数第一个比较
}
int sum=0;
for(int i=0;i<x;++i)
{
sum+=Math.min(leftmax[i],rightmax[i])-height[i];//取同个地方左右遍历两边最小的与本身高度相减,最后相加
}
return sum;
}
}

这里附上我的解释:首先判断这个需要的长度,然后判断是否长度等于0,不等于0的话,进行左遍历,互相比较,最高的输出,覆盖在数组上,也就是leftmax【里面的长度的数组】都等于找到的最高值,右遍历也一样,然后,数组一样的左遍历与右遍历中取min,然后减去这个数组下,该有的高度。得出结果
这个方式是动态输出