leetcode 42.接雨水 │ 汪福翔

题目描述

给定一个非负整数数组 height，表示一个由若干条连续的水平线段构成的柱状图，其中每个线段的左侧和右侧都是无限长的。假设从上方有雨水落下，计算直到雨水与柱状图的某个线段相接时，线段能够接住的雨水量。

示例 1:

输入: height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
解释: 上面是由数组表示的形状，其中 "X" 表示积水的位置。总的积水量为 6。

示例 2:

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

题解

这个问题可以通过双指针法解决。首先，我们找到左侧和右侧最高的柱子，然后向中间移动指针，每次移动都更新当前位置左右两侧的最高柱子，从而计算出当前位置能够接住的雨水量。

下面是使用 Go 语言实现的代码：

package main

import "fmt"

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

	for left < right {
		if leftMax < rightMax {
			left++
			leftMax = max(leftMax, height[left])
			ans += leftMax - height[left]
		} else {
			right--
			rightMax = max(rightMax, height[right])
			ans += rightMax - height[right]
		}
	}

	return ans
}

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

func main() {
	fmt.Println(trap([]int{0,1,0,2,1,0,1,3,2,1,2,1})) // 输出: 6
	fmt.Println(trap([]int{4,2,0,3,2,5}))               // 输出: 9
}

复杂度分析

时间复杂度：O(n)，其中 n 是数组 height 的长度。我们只需要遍历一次数组即可。
空间复杂度：O(1)，我们只使用了常数级别的额外空间。

#leetcode