leetcode42 接雨水

题目

给定 n 个非负整数表示每个宽度为 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 个单位的雨水（蓝色部分表示雨水）。

解析

这道题可以有暴力法、动态规划法、单调栈法、双指针法等，由于上一道题是用的双指针，为了好记，这里也使用双指针法。
先贴一个讲的比较好的视频：视频讲解
这道题使用双指针，主要的思路是：比如上图中的最高的那块木板，左边的位置能解多少雨水，取决于它左边木板的最大高度，因为低于这个最大高度是会漏出去的。
基础版的双指针，需要两个额外的数组，一个存从左边开始到i的最大高度，一个存从右边开始的。计算的方法就是比较前一时刻的最大值和此刻的比较，然后取max。这个时候就有了两个数组，取min后和本身的数组比较，就是能接的最大容量

func trap(height []int) (ans int) {
    n := len(height)
    preMax := make([]int, n) // preMax[i] 表示从 height[0] 到 height[i] 的最大值
    preMax[0] = height[0]
    for i := 1; i < n; i++ {
        preMax[i] = max(preMax[i-1], height[i])
    }

    sufMax := make([]int, n) // sufMax[i] 表示从 height[i] 到 height[n-1] 的最大值
    sufMax[n-1] = height[n-1]
    for i := n - 2; i >= 0; i-- {
        sufMax[i] = max(sufMax[i+1], height[i])
    }

    for i, h := range height {
        ans += min(preMax[i], sufMax[i]) - h // 累加每个水桶能接多少水
    }
    return
}

func min(a, b int) int { if a > b { return b }; return a }
func max(a, b int) int { if a < b { return b }; return a }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

如果不想开辟两个新组数，那么就使用两个单纯的指针，分别从左右开始遍历，那么此刻我们知道，比如左右都遍历了两个位置，那么中间位置的容量我们是不知道的，但是如果前缀最大值比后缀最大值小，那么左边木桶的容量就是前缀最大值的容量，算完后向右扩展；同理如果后缀最大值比前缀最大值小，那么右边这个木桶的容量就是后缀最大值的容量。。。

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

func max(a, b int) int{
    if a > b {
        return a
    }
    return b
}
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