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.
For example, Given [0,1,0,2,1,0,1,3,2,1,2,1]
, return
6
.
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!
the key problem is Get B[i] and C[i] ,where B[i] means the max forward, and C[i] means max backward.
Sum += Min(B[i] ,C[i])-A[i] >0?Min(B[i] ,C[i])-A[i]:0
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 |
class
Solution { public : int
trap( int
A[], int
n) { int * B = new
int [n]; int
sum = 0; int
max= 0; for ( int
i = 0 ;i<n;i++) { B[i]=max; if (max < A[i]) { max=A[i]; } } max =0 ; for ( int
i=n-1; i>=0 ;i--) { int
h = B[i]; if (B[i] > max) { h = max; } if (A[i] < h) { sum += h-A[i]; } if (max < A[i]) { max=A[i]; } } delete [] B; return
sum; } }; |
[LeetCode] [Trapping Rain Water 2012-03-10],布布扣,bubuko.com
[LeetCode] [Trapping Rain Water 2012-03-10]
原文:http://www.cnblogs.com/xxiao1119/p/3742097.html