⚔ LeetCode | 42. Trapping Rain Water

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

Problem

Trapping Rain Water - LeetCode

Difficulty : Hard

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

img

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example:

1
2
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Analysis

这道题给出一个数组，代表着墙体的高度，需要求出这些墙体里面最多可以多大体积的水。

Approach 1

首先，我一开始想到的是对这个数组从左到右进行遍历，对于每一个元素，寻找其左右的最大值，然后左右最大值之中的较小值和当前的高度的差就是当前格子可以装水的体积，然后在加起来就是所有格子装水的体积。这看上去就是一个最暴力的算法。

对于第i个格子，高度为h

在0到i - 1中，找到最大值lMax

在i + 1到n - 1中，找到最大值rMax

这个格子所可以容纳的水量就为Min(lMax, rMax) - h

然后把所有格子可以容纳的水量的和加起来，就是答案

代码如下：

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
28
func trap2(height []int) int {
	all := len(height)
	if all < 3 {
		return 0
	}
	water := 0
	for i := 1; i < all - 1; i++ {
		l, r := i - 1, i + 1
		for j := l; j >= 0; j-- {
			if height[j] > height[l] {
				l = j
			}
		}
		for j := r; j < all; j++ {
			if height[j] > height[r] {
				r = j
			}
		}
		if height[l] > height[i] && height[i] < height[r] {
			if height[l] > height[r] {
				water += height[r] - height[i]
			} else {
				water += height[l] - height[i]
			}
		}
	}
	return water
}

但是这个算法的复杂度是O(n^2)的，在LeetCode上花费了140ms，仅仅超越了3.57%的提交，因此应该会有更好的解决方案

Approach 2

上面的算法是对于每个格子都需要找其两边的最大值，也就是对于数组里面每个元素需要进行一次O(n)的操作，这是十分耗时的。

其实我们可以一开始就从两边的最大值入手，逐渐逼近中间，那么算法的复杂度就可以大大降低了。

假设当前左边的最大值为lMax(比它左边的所有格子都要高)， 右边的最大值为rMax(比它右边的所有格子都要高)

那么可以判断出l或者r的位置的格子的水的容量吗？

答案是可以的。

我们来看一下几种情况：

  • l的高度大于或等于lMax：l的水的容量为 0，因为左边的所有格子都是比l低的（lMax已经比左边所有格子都要高），因此，水会从左边全部流出，这个格子不能装到水。
  • r的高度大于或等于rMax：r的水的容量为 0，理由同上。
  • l的高度小于lMax：这种情况下就比较复杂，因为你只是知道了lMax是左边的最高的高度，而右边最高的高度是未知的，这种情况下面再详细讨论
  • r的高度小于rMax：同理，这种情况下也是不明确的。

上面四种情况中，有两种是确定的，而还有两种是不确定的，那么如何想办法将这两种情况确定下来呢？

既然是从两边不断逼近，那么我们可以从逼近的方向上入手。

最好的策略就是先从比较低的方向收缩

从左右两边当前的高度来看，可以对于上面两种不能确定的情况来看，又可以分为两种情况（假设上面第 3 种或第 4 种情况成立的时候）：

  • l的高度比r高，因此从r这边收缩：
    • r的高度小于rMax：r是可以确定的，因为当前rMax就是右边的最高，而左边的最高不管是lMax还是一个比lMax更大的值也无所谓，因为 我们是从比较低的方向开始收缩的，因此可以判定当前的lMax必定比rMax要大， r格子所容纳的值是取决于他们之间较小的那个值，因此，r所可以容纳的水量为rMax - height[r]
    • l的高度小于lMax：这种情况下，l的容量是不明确的，因为你只是知道了左边的最大值，而右边是否存在一个比rMax更大的格子是不知道的，因此尽管当前左边是比右边高的，但是当前格子的最大容量还是不明确。
  • 同理，当r的高度大于l的时候，在l的高度小于lMax的情况下，就可以判断出l所容纳的水量为lMax - height[l]

这样一来，我们就可以不断收缩范围，一直判断到l与r重叠。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func trap(height []int) int {
	all := len(height)
	lMax, rMax := 0, 0
	l, r := 0, all - 1
	water := 0
	for l < r {
		if height[l] < height[r] {
			if height[l] > lMax {
				lMax = height[l]
			} else {
				water += lMax - height[l]
			}
			l++
		} else {
			if height[r] > rMax {
				rMax = height[r]
			} else {
				water += rMax - height[r]
			}
			r--
		}
	}
	return water
}

这种算法只需要对数组遍历一次，因此复杂度为O(n)，极大地降低了算法的复杂度，在LeetCode上可以达到4ms(100%)的运行时间。

Summary

这道题虽然被标记为Hard，但是实际上并不难，只要知道如果算每个格子的水的面积，就可以解出答案，唯一的难点就在于如果快速地有效率地扫描所有的格子，以最快的速度找出答案。主要是用到了两边逼近的思想，同时从两边出发，根据规则，快速判定出当前格子可以容纳的水的体积。

土豪通道
0%