LeetCode-42.接雨水 - sheep44044的小站

双指针#

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

示例 1：

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

示例 2：

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

1.Gemini的方法

第一道困难题，果然还是做不出来…不过知道了思路后，难度会减少很多

思路: 每个柱子能积多少水取决于左右两侧第二高的柱子，柱子自身被包括在其中一个边界中，这是正确的，但从理解上有时感觉很奇怪

1
func trap(height []int) int {
2
    left, right := 0, len(height) - 1
3
    leftmax, rightmax := 0, 0
4
    res := 0
5

6
    for left < right {
7
        leftmax = max(leftmax, height[left])
8
        rightmax = max(rightmax, height[right])
9

10
        if leftmax < rightmax {
11
            res += leftmax - height[left]
12
            left++
13
        }else{
14
            res += rightmax - height[right]
15
            right--
16
        }
17
    }
18

19
    return res
20
}

2.评论区翻到的思路

对于初学者，其实这个思路挺简单的，很容易理解，我就按照评论区中顺着思路用Go写下来了。

不过理解后其实还是第一种更好的

思路:将实例图中的蓝色也看成实心的，算出每一层的面积，加起来，然后减去height的总和，剩下的就是水量。

1
func trap(height []int) int {
2
    left, right := 0, len(height) - 1
3
    area := 0
4
    sum := 0
5
    maxH := 0
6

7
    for _, h := range height {
8
        sum += h
9
        if h > maxH {
10
            maxH = h
11
        }
12
    }
13

14
    for h := 1; h <= maxH; h++ {
15
        for left < len(height) && height[left] < h {
16
            left++
17
        }
18

19
        for right >= 0 && height[right] < h {
20
            right--
21
        }
22

23
        if left > right {
24
            break
25
        }
26
        area += right - left + 1
27
    }
28

29
    return area - sum
30
}