接雨水
问题描述：
如上图所示，海拔分别为 [0,1,0,2,1,0,1,3,2,1,2,1], 返回 6。
运行时间：1635ms
接雨水
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class Solution {
/**
* @param heights: an array of integers
* @return: a integer
*/
public int trapRainWater(int[] heights) {
int sum=0;
int index=0;
int k=0;
int mintemp=0;
for(int i=0;i<heights.length-1;){
if(heights[i]<=heights[i+1]){
i++;
continue;
}
else{
index=find(heights,heights[i],i+1);
if(index==0){
break;
}
k=i+1;
mintemp=Math.min(heights[i],heights[index]);
while(k<index){
sum+=mintemp-heights[k];
k++;
}
i=index;
}
}
return sum;
}
public int find(int[] heights,int temp,int i){
int max=0;
int index=0;
int k=i;
int count=0;
for(;i<heights.length;i++){
if(i+1<heights.length&&heights[i]>=heights[i+1]){
count++;
}
if(heights[i]>max){
max=heights[i];
index=i;
}
if(heights[i]>=temp){
return i;
}
}
if(count==heights.length-k){
return 0;
}
return index;
}
}