接雨水

问题

https://leetcode-cn.com/problems/trapping-rain-water

给定 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 ，它能否接住雨水取决于它两侧 data[:i-1] 和 data[i+1:] 的最大的较小的一处。

记 lMax 为 data[:i-1] 的最大值，rMax 为 data[i+1:] 的最大值。

若 lMax、rMax 有一个比 data[i] 小，则 i 处肯定接不到雨水。 若 lMax、rMax 都比 data[i] 大，则 i 处接到雨水的量为 min(lMax,rMax)-data[i]。

通过上面的推导，整个 data 能接住的雨水量就是上面结果的累加值。

暴力遍历

package main

import (
	"fmt"
)

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

func getRainAmount(data *[]int) int {
	result := 0
	for i := 0; i < len(*data); i++ {

		// 找到左边最大的高度
		lMax := 0
		if i > 0 {
			for j := 0; j < i; j++ {
				if (*data)[j] > lMax {
					lMax = (*data)[j]
				}
			}
		}

		// 找到右边最大的高度
		rMax := 0
		for k := i + 1; k < len(*data); k++ {
			if (*data)[k] > rMax {
				rMax = (*data)[k]
			}
		}
		tmp := min(lMax, rMax)
		if tmp > (*data)[i] {
			// 两边都比自己高，才能接的住雨水
			result += tmp - (*data)[i]
		}

	}

	return result
}

func main() {
	data := []int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}
	fmt.Printf("data:%v \n", data)
	r := getRainAmount(&data)
	fmt.Printf("result:%v \n", r) // result:6
}

上面有提到“两边都比自己高，才能接的住雨水”，可以把 data[i] 算进比较中，每次增加 tmp-data[i] 即可。优化如下：

func getRainAmount(data *[]int) int {
  if len(*data) == 0 {
		return 0
	}
	result := 0
	for i := 0; i < len(*data); i++ {

		// 找到左边最大的高度
		lMax := (*data)[i]
		if i > 0 {
			for j := 0; j < i; j++ {
				if (*data)[j] > lMax {
					lMax = (*data)[j]
				}
			}
		}

		// 找到右边最大的高度
		rMax := (*data)[i]
		for k := i + 1; k < len(*data); k++ {
			if (*data)[k] > rMax {
				rMax = (*data)[k]
			}
		}
		result += min(lMax, rMax) - (*data)[i]
	}

	return result
}

上面的时间复杂度有 \(O(n^2)\)，空间复杂度为 \(O(1)\)。

使用备忘录

上面的解法中存在重复的遍历，增大了时间复杂度。

例如：查找 data[5] 和 data[4] 左侧的最大值时，都遍历了 data[:4] 。可以把每个位置 i 处左侧的最大值记下来，计算 i+1 处左侧最大值时可以直接比较 lMax[i] 和 data[i+1] 的大小，最大值设为 lMax[i+1]。同理，右侧最大值也是。

上面暴力法可以优化如下：

package main

import (
	"fmt"
)

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

func getRainAmount(data *[]int) int {
	if len(*data) == 0 {
		return 0
	}

	// 左侧最大值备忘录，lMaxMemo[i] 表示i处左侧，包含i，最大的值
	lMaxMemo := []int{(*data)[0]}
	for i := 1; i < len(*data); i++ {
		lMaxMemo = append(lMaxMemo, max((*data)[i], lMaxMemo[i-1]))
	}
	fmt.Printf("lMaxMemo:%v \n", lMaxMemo)

	// 右侧最大值备忘录，rMaxMemo[i] 表示i处右侧，包含i，最大的值
	rMaxMemo := []int{}
	for i := 0; i < len(*data); i++ {
		// 初始化并填充0
		rMaxMemo = append(rMaxMemo, 0)
	}
	// 初始化最右侧的值
	rMaxMemo[len(*data)-1] = (*data)[len(*data)-1]

	for i := len(*data) - 2; i >= 0; i-- {
		rMaxMemo[i] = max((*data)[i], rMaxMemo[i+1])
	}
	fmt.Printf("rMaxMemo:%v \n", rMaxMemo)

	result := 0
	for i := 0; i < len(*data); i++ {
		result += min(lMaxMemo[i], rMaxMemo[i]) - (*data)[i]
	}

	return result
}

func main() {
	data := []int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}
	fmt.Printf("data:%v \n", data)
	r := getRainAmount(&data)
	fmt.Printf("result:%v \n", r) // result:6
}

此时，时间复杂度降为了 \(O(n)\)，空间复杂度升为了 \(O(n)\)。用空间的消耗减少了时间的消耗。

双指针

当 lMax < rMax 时，积水的深度依赖于 lMax，相反依赖于 rMax。

可以定义两个指针 left 和 right，分别指向数组的两端，向中间遍历。lMax 作为 left 左侧的最大值，rMax 作为 right 右侧的最大值。

当 lMax < rMax 时，rMax 不一定是 left 右侧最大值，但 lMax 一定是 left 左侧最大值，即 left 更信任 lMax，我们可以让 left向右移动。反之如是。

解法如下：

package main

import (
	"fmt"
)

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

func getRainAmount(data *[]int) int {
	if len(*data) == 0 {
		return 0
	}

	result := 0
  // 左指针
	left := 0
  // 右指针
	right := len(*data) - 1
	// 初始化某位置左侧最大值
	lMax := (*data)[left]
	// 初始化某位置右侧最大值
	rMax := (*data)[right]

	for left <= right {
		lMax = max((*data)[left], lMax)
		rMax = max((*data)[right], rMax)

		if lMax < rMax {
			// 左低右高
			result += lMax - (*data)[left]
			left++
		} else {
			// 左高右低
			result += rMax - (*data)[right]
			right--
		}
	}
	return result
}

func main() {
	data := []int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}
	fmt.Printf("data:%v \n", data)
	r := getRainAmount(&data)
	fmt.Printf("result:%v \n", r) // result:6
}

时间复杂度：\(O(n)\)，空间复杂度： \(O(1)\)。