Trapping Rain Water
Description
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!
Solution
每个点容量决定于左右两边高度
先从左往右，扫描出每个点左边最高的围栏
再从右往左，扫描出每个点右边最高的围栏
在围栏比当前点高的情况下， 这个点的容量为围栏高度减底部高度: min(left_height, right_height) - bottom
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
|
func trap(height []int) int {
var record int
var result int
length := len(height)
if length < 3 {
return 0
}
leftHeight := make([]int, length)
record = height[0] // record the max height of left positions
// scan left height for each position
for i := 0; i < length-1; i++ {
leftHeight[i] = record
n := height[i]
if n > record {
record = n
}
}
record = height[length-1] // record the max height of right positions
for i := length - 2; i >= 0; i-- {
h := min(record, leftHeight[i])
n := height[i]
if h > n {
// have some water
result += (h - n)
}
if n > record {
record = n
}
}
return result
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
|
Similar Problem
11. Container With Most Water
