计算装水量
描述
给定n个非负整数表示每个柱的宽度为1的高程图，计算下雨后能够捕获的水量。
例如 [0,1,0,2,1,0,1,3,2,1,2,1]
样例
样例11
2输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
样例21
2输入: [5,2,1,2,1,5]
输出: 14
思路
找一块最高的，从左边遍历，再从右边遍历。也可以找两块挡板，最左和最右各一块。
代码
一块挡板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
36class Solution {
public:
int trap(vector<int>& height) {
int ans = 0;
// Find the max height and index
int maxIdx=0;
int maxHeight = 0;
for(int i=0;i<height.size();i++){
if( maxHeight < height [i]){
maxHeight = height[i];
maxIdx = i;
}
}
// Go through from left to the highest bar
int preHeight = 0;
for(int i=0;i<maxIdx;i++){
if(height[i]>preHeight){
preHeight = height[i];
}
ans += preHeight-height[i];
}
// Go through from right to the highest bar
preHeight = 0;
for(int i=height.size()-1;i > maxIdx;i--){
if(height[i]>preHeight){
preHeight = height[i];
}
ans += preHeight-height[i];
}
return ans;
}
};
两块挡板1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
int trap(vector<int>& height) {
int res=0;
int lmax=0, rmax=height.size()-1;
int l=1, r=height.size()-2;
while(l<=r){
if(height[lmax]<height[rmax]){
height[lmax]>height[l] ? res+=height[lmax]-height[l] : lmax=l;
l++;
}
else{
height[rmax]>height[r] ? res+=height[rmax]-height[r] : rmax=r;
r--;
}
}
return res;
}
};
乱来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
65
66
67
68
69
70
71
72
73class Solution {
public:
int trap(vector<int>& height) {
if(height.size()<=2){return 0;}
vector <int> moutain;
int ans = 0;
int addflag = 1;// 0代表当前为递减，1代表当前为递增
int start = height.size()-1;
for(int i=1;i<height.size();i++){
if(height[i] < height[i-1]){
start = i-1 ;
break;
}
}
// moutain.push_back(start);
start = std::max(1,start);
cout << "start "<< start <<endl;
// system("pause");
for(int i=start;i<height.size();i++){
if(addflag == 1 && height[i] < height[i-1]){
// cout <<"峰值下标为 "<< i -1 <<endl;
moutain.push_back(i-1);
addflag = 0;
}
else if(addflag == 0 && height[i] > height[i-1]){
addflag = 1;
if(i==height.size()-1){
moutain.push_back(i);
}
}
}
cout<<moutain.size()<<endl;
if(moutain.size() <2){ return 0 ;}
cout <<"峰值下标为 ";
for(int i=0;i<moutain.size();i++){
cout << moutain[i] <<"\t";
}
cout<<endl;
int left = 0;
int right = moutain.size()-1;
while(left<right){
int temp = ans;
int minHeight = 0;
int i ;
if(moutain[left] > moutain[right]){
minHeight = moutain[right];
i = right -1;
right = right -1;
}
else{
minHeight = moutain[left];
i = left;
left = left+1;
}
for(int j = moutain[i]+1;j<moutain[i+1];j++){
if(minHeight > height[j] ){
ans += abs(minHeight-height[j]);
}
}
printf("第%d个和第%d个得到的结果为%d,minHeight为%d\n",i,i+1,ans -temp,minHeight );
}
return ans;
}
};