-
Notifications
You must be signed in to change notification settings - Fork 0
/
42. Trapping Rain Water
64 lines (50 loc) · 1.89 KB
/
42. Trapping Rain Water
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
56
57
58
59
60
61
62
63
64
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
solution :
class Solution {
public:
int trap(vector<int>& height)
{
int num=0;
cac(num,0,height.size()-1,height);
return num;
}
void cac(int & num,int maxl,int maxr,vector<int>& height) //计算maxl到maxr间的雨滴数
{
if(maxl>=maxr)
return ;
int mid; //找到最高的
mid=findhigh(maxl,maxr,height);
int midleft,midright;
if(mid!=maxl) //最高的不在最左边,在左边找次高的,并算出总雨量
{
midleft=findhigh(maxl,mid-1,height);
cac(num,0,midleft,height);
num+=(mid-midleft-1)*height[midleft];
for(int i=midleft+1;i<mid;i++)
num-=height[i];
}
if(mid!=maxr) //最高的不在最右边,在右边找次高的,并算出总雨量
{
midright=findhigh(mid+1,maxr,height);
cac(num,midright,height.size()-1,height);
num+=(midright-mid-1)*height[midright];
for(int i=mid+1;i<midright;i++)
num-=height[i];
}
}
int findhigh(int maxl,int maxr,vector<int>& height)
{
int i;
int max=maxl;
for(i=maxl;i<=maxr;i++)
{
if(height[max]<height[i])
max=i;
}
return max;
}
};