42. 接雨水

题目描述

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

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

n == height.length
1 <= n <= 2 * 10⁴
0 <= height[i] <= 10⁵

解法一：动态规划

 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


func trap(height []int) (ans int) {
    n := len(height)
    if n == 0 {
        return
    }

    leftMax := make([]int, n)
    leftMax[0] = height[0]
    for i := 1; i < n; i++ {
        leftMax[i] = max(leftMax[i-1], height[i])
    }

    rightMax := make([]int, n)
    rightMax[n-1] = height[n-1]
    for i := n - 2; i >= 0; i-- {
        rightMax[i] = max(rightMax[i+1], height[i])
    }

    for i, h := range height {
        ans += min(leftMax[i], rightMax[i]) - h
    }
    return
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

解法二：单调栈

维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标在 heights 数组中指向的元素递减。

 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


func trap(height []int) int {
    var stack []int
    res := 0
    for i := 0; i < len(height); i++ {
        for len(stack) > 0 && height[stack[len(stack)-1]] < height[i] {
            idx := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if len(stack) <= 0 {
                break
            }
            left := stack[len(stack)-1]
            width := i - left - 1
            lower := min(height[i], height[left])
            res += width * (lower - height[idx])
        }
        stack = append(stack, i)
    }
    return res
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

解法三：双指针

 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


func trap(height []int) int {

    var max = func(x, y int) int {
        if x < y {
            return y
        }
        return x
    }

    n := len(height)
    leftMax, rightMax := height[0], height[n-1]
    left, right := 1, n-2
    sum := 0
    count := n - 2
    for count > 0 {
        if leftMax > rightMax {
            if height[right] < rightMax {
                sum += rightMax - height[right]
            }
            rightMax = max(rightMax, height[right])
            right--
        } else {
            if height[left] < leftMax {
                sum += leftMax - height[left]
            }
            leftMax = max(leftMax, height[left])
            left++
        }
        count--
    }
    return sum
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


func trap(height []int) int {
    left, right := 0, len(height) - 1
    leftMax, rightMax := 0, 0
    res := 0
    for left < right {// 改为 left <= right 也能通过，为什么？
        leftMax = max(height[left], leftMax)
        rightMax = max(height[right], rightMax)
        if height[left] < height[right] {
            res += leftMax - height[left]
            left++
        } else {
            res += rightMax - height[right]
            right--
        }
    }
    return res
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

思考：上面代码由 left < right 改为 left <= right 也能通过的原因是什么？

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func trap(height []int) int {
    n := len(height)
    leftMax, rightMax := height[0], height[n-1]
    left, right, ans := 1, n-2, 0
    for left <= right {
        if leftMax < rightMax {
            if height[left] < leftMax {
                ans += leftMax - height[left]
            } else {
                leftMax = height[left]
            }
            left++
        } else {
            if height[right] < rightMax {
                ans += rightMax - height[right]
            } else {
                rightMax = height[right]
            }
            right--
        }
    }
    return ans
}