如图

最朴素的一种解法,使用动态规划~

维护一个一维的dp数组,这个DP算法需要遍历两遍数组,第一遍遍历dp[i]中存入i位置左边的最大值,然后开始第二遍遍历数组,第二次遍历时找右边最大值,然后和左边最大值比较取其中的较小值,然后跟当前值A[i]相比,如果大于当前值,则将差值存入结果

直接贴代码:

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
func trap(height []int) int {

rs := 0
mx := 0
n := len(height)
dp := make([]int,n)

for i := 0; i < n; i++ {
dp[i] = mx
mx = max(mx,height[i])
}

mx = 0

for i := n-1; i >= 0; i-- {
dp[i] = min(dp[i],mx)
mx = max(mx,height[i])
if dp[i] - height[i] > 0 {
rs += dp[i] - height[i]
}
}
return rs

}


// golang max int
func max(first int, args... int) int {
for _ , v := range args{
if first < v {
first = v
}
}
return first
}


// golang min int
func min(first int, args... int) int {
for _ , v := range args{
if first > v {
first = v
}
}
return first
}

运行结果:

如图

总结:

显然,这还不是最优解法