0%

trapping-rain-water

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

题解

几乎一次过,受宠若惊啊哈哈哈哈

感觉没啥难的地方啊,就看图写代码

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
int trap(vector<int>& height) {
int res = 0;
int vsize = height.size();
if (vsize < 3)return 0;
while (height[0] <= height[1])
{
height.erase(height.begin());
vsize--;
if (vsize < 3)return 0;
}
while (height[vsize - 1] <= height[vsize - 2])
{
height.erase(height.end() - 1);
vsize--;
if (vsize < 3)return 0;
}
int t1 = 0;
int t2 = t1 + 1;
while (t2<vsize)
{
int h_sum = 0;
while (t2 < vsize&&height[t2] < height[t1])
{
h_sum += height[t2];
t2++;
}
if (t2 < vsize)
{
if (t2 - t2>1)
res = res + height[t1] * (t2 - t1 - 1) - h_sum;
t1 = t2;
}
t2++;
}
int limit = t1;
t1 = vsize - 1;
t2 = t1 - 1;
while (t2 >= limit)
{
int h_sum = 0;
while (t2 >= limit && height[t2] < height[t1])
{
h_sum += height[t2];
t2--;
}
if (t2 >= limit)
{
if(t1 - t2>1)
res = res + height[t1] * (t1 - t2 - 1) - h_sum;
t1 = t2;
}
t2--;
}
return res;
}