【LeetCode】42. 接雨水 - Go 语言题解

---

一、题目描述

给定 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 * 104
0 <= height[i] <= 105

题目链接：https://leetcode.cn/problems/trapping-rain-water/

---

二、题解一

1. 思路

每一处柱子能够存储的水量取决于其左边最高的柱子和其右边最高的柱子中比较矮的那一个的高度减去其自身的高度。

那么我们创建两个数组，left_height 和 right_height 分别存储当前柱子左边的最高柱子高度和当前柱子右边的最高柱子高度。

然后取出当前位置的 left_height 和 right_height 中比较矮的那一个，减去当前位置的柱子本身的高度。

再相加就是总的水量。

2. Golang 代码

func trap(height []int) int {
    
    left_height := []int{
    }
    left_max := 0
    for _,i := range height{
    
        if i > left_max{
    
            left_max = i
            left_height = append(left_height,i)
        }else{
    
            left_height = append(left_height,left_max)
        }
    }
    fmt.Println(left_height)

    right_height := make([]int,len(height))
    right_max := 0

    for i := len(height)-1; i>-1; i--{
    
        if height[i] > right_max{
    
            right_max = height[i]
            right_height[i] = height[i]
        }else{
    
            right_height[i] = right_max
        }
    }
    fmt.Println(right_height)

    rain := 0
    for i := 0; i<len(height); i++{
    
        rain += min(left_height[i],right_height[i])-height[i]
    }

    return rain

}

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

---

三、题解二：双指针

上面的方法时间复杂度和空间复杂度都比较高。（搜索三次，新增存储两个切片）

以下是使用双指针的改进方法。（只搜索一次，新增存储三个整数）

1. 思路

通过观察，我们发现：

1. 在低洼处（两边高）会形成积水
2. 积水高度取决于两边最高的墙壁中比较低的那一个

从 2 的直觉出发，从两边开始搜索，哪边比较低，就把哪边的指针向前移动，进行搜索，另一个不动的指针指向的是当前最高的墙壁。

同时，设置 max 记录当前最高水位，也就是正在搜索的这一边中，搜索过的最高值。

每搜索一个位置，总的水量都增加 max - height[当前位置]。

2. Golang 代码

func trap(height []int) int {
    
   
    i := 0
    j := len(height)-1

    rain := 0
    max := 0

    //直到两指针相遇
    for i < j {
    
        //i这边比较矮，就将i向前移动
        if height[i] <= height[j]{
    
            //特殊判断，i处于起始位置
            if i == 0 {
      
                max = height[i]
                i++
                continue
            }
            //特殊判断，遇到更高的柱子
            if height[i] > max{
    
                max = height[i]
            }
            rain +=  max - height[i]
            i++
        }else{
      //j这边比较矮，就将j向前移动
            //特殊判断，j处于起始位置
            if j == len(height)-1 {
    
                max = height[j]
                 j--
                continue
            }
            //特殊判断，遇到更高的柱子
            if height[j] > max{
    
                max = height[j]
            }
            rain += max - height[j]
            j--
        }
    }
    
   return rain

}

评判结果：