Ltd的算法大抄·接雨水的各种姿势

这是算法记录的第14天，这篇主要解决42.接雨水问题

这道题应该是非常经典的面试题，而字节似乎更情有独衷，一些交流群里甚至流传着字节的HR都会接雨水的骇闻，上一次字节的青训营也是直接魔改成了接青豆。由于上次仅使用了单调栈实现，细节也有些遗忘，所以为了进一步理解、掌握这道题，这里单独一篇文章，就记录下接雨水的各种方式，以加深印象。

题目

给定 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

整体思路

不论以什么可行解法，这道题都需要先以分解问题的思路入手，确定好是按行分还是按列分（有点像二重积分选x-y型域），按什么顺序去分，总不至于这里横一块、那里竖一块，凑到一起又是一块。

后面的方式基本是从左往右依次求出每列的接水量。

明确一下问题，我们现在要求的就是每一列能存多少雨水，然后不断累加就是总的接雨水量。

输入的height是一个表示对应索引柱子高度的数组，而左右两边不同的柱子就围成中间能接雨水的凹槽。柱子越高，围的空间肯定更大，所以问题转换为了要确定出当前的左右两边分别最高的柱子l和r。

最后，由于水桶效应，存的水量始终是没法超过l和r中较小的那一个，所以此时的高度就是h = min(l, r)。

但需要注意有些列本身是有柱子的，所以存水量就是height[i] - h。这个很好理解，极端情况就是当前列的柱子就是min(l, r)那个，所以就没有存水的地方了。

暴力

思路

如何求出左右两边的最高柱子？暴力。既然是暴力解法，那么就是不带脑子的对所有可能性一个个地试探找到最后的答案——对每列在求其接水量的时候都通过遍历去找到左右分别最高的就行。

很显然，这种方式的时间复杂度是O(n^2)。

代码

// 暴力解法
// 执行耗时:748 ms,击败了5.01% 的Go用户
// 内存消耗:5.1 MB,击败了64.20% 的Go用户
func trapByForce(height []int) int {
	n := len(height)
	res := 0
	//左右两端的不用求，所以索引范围是[1,n-1)
	for i := 1; i < n-1; i++ {
		lMax, rMax := 0, 0
		// 找左边最高的柱子
		for j := i; j >= 0; j-- {
			lMax = max(lMax, height[j])
		}
		// 找右边最高的柱子
		for j := i; j < n; j++ {
			rMax = max(rMax, height[j])
		}
		// 当前列的柱子就是较低的那个的话
		// height[i] = min(lMax, rMax)
		// min(lMax, rMax) - height[i] = 0
		res += min(lMax, rMax) - height[i]
	}
	return res
}
// min&max省略

动态规划

思路

上面的暴力解法之所以复杂度高就是在遍历的时候每个位置都计算了rMax和lMax，假如提前计算并记录每个位置的rMax和lMax，就能在遍历的时候直接使用了，就像备忘录一样。

关键是如何在低于O(n^2)的时间获得这个备忘录——毕竟是要降低时间复杂度，所以考虑使用动态规划。

和递归相似，弄清楚之前的已经完成了什么，当前需要完成什么。

对于lMax，从左到右计算，那么已经认定求出左边最大的了，当前的lMax[i]就由上一个lMax[i-1]和height[i]中更大的一个确定，这样一次遍历就能获取lMax；

对于rMax，从右到左计算，那么已经认定求出右边最大的了，当前的rMax[i]就由上一个rMax[i+1]和height[i]中更大的一个确定，这样一次遍历也就能获取rMax。

递推方程如下：

当 1≤i≤n−1 时，lMax[i]=max(lMax[i−1],height[i])；

当 0≤i≤n−2 时，rMax[i]=max(rMax[i+1],height[i])。

代码

// 动态规划-备忘录
// 执行耗时:12 ms,击败了56.16% 的Go用户
// 内存消耗:5.9 MB,击败了37.20% 的Go用户
func trapByDP(height []int) int {
	if len(height) == 0 {
		return 0
	}
	n := len(height)
	res := 0
	// 切片充当备忘录
	lMax := make([]int, n)
	rMax := make([]int, n)
	// 初始化边界情况
	lMax[0] = height[0]
	rMax[n-1] = height[n-1]
	// 从左向右计算 lMax
	for i := 1; i < n; i++ {
		lMax[i] = max(lMax[i-1], height[i])
	}
	// 从右向左计算 rMax
	for i := n - 2; i >= 0; i-- {
		rMax[i] = max(rMax[i+1], height[i])
	}
	// 计算答案
	for i := 1; i < n-1; i++ {
		res += min(lMax[i], rMax[i]) - height[i]
	}

	return res
}
// min&max省略

双指针

思路

基本思路还是一样，不过使用了双指针进行移动，而不是单纯的从左往右依次遍历。

同时，定义左右指针两边的最大值lMax和rMax分别表示height[0,l]和height[r,...]。

这两个参数上面的方法是定义来表示height[i]的左右两边最大值，那样能够覆盖整个数组；而这里只是覆盖了height中(l,r)以外的部分。

具体细节结合注释

代码

// 双指针
// 执行耗时:8 ms,击败了91.92% 的Go用户
// 内存消耗:5.1 MB,击败了92.87% 的Go用户
func trapByDoublePointer(height []int) int {
	// 定义左右指针
	l, r := 0, len(height)-1
	// 定义左右指针两边的最大值: lMax = height[0,l]; rMax = height[r,...]
	lMax, rMax := height[l], height[r]
	res := 0
	// 左右指针每次只有一个移动，表示那个位置的已经求出来了
	for l < r {
		// 只需要知道较小的就行，一旦满足这个条件，不需要关注另一边的情况，因为从全局来看这部分一定会被“接”到
		if lMax < rMax {
			res += lMax - height[l]
			l++                         // 当前左指针所指的位置已经计算了，右移
			lMax = max(lMax, height[l]) // 放在这里是避免求另一个的时候重复无意义比较
		} else {
			res += rMax - height[r]
			r--                         // 当前右指针所指的位置已经计算了，左移
			rMax = max(rMax, height[r]) //同样，放在这里是避免求另一个的时候重复无意义比较
		}
	}
	return res
}
// min&max省略

单调栈

思路

栈的解法类似于括号匹配，每次匹配出一对括号（即找到匹配的两柱），再计算这两柱中间能接的水量。

单调栈又是什么？之前有一道题是用了单调队列来求滑动窗口的最大值，其实就是抛开了无关的部分，只保留需要计算的那部分。而这里使用单调栈，首先是确保栈中元素（也就是数组下标）对应的值是从栈底到栈顶递减的。对于新的位置，遇到比栈顶小的就入栈，遇到比栈顶大的就出栈。

为了便于表述，

• 用topV表示栈顶索引的高度，即height[top]；
• 用current表示指向当前遍历位置的指针；
• 用currentV表示当前位置的高度。

具体而言就是用栈来保存数组的下标，从最左边出发，

• 若currentV大于topV，出栈并对这两柱之间的雨水量进行累加，接着循环比较currentV和新栈的topV，直至currentV小于等于topV或者是栈都已经空了就退出循环比较——确保栈内的是单调的，最后就是把当前的入栈，current后移；
• 若currentV小于等于topV，就把当前位置入栈，current后移一位，继续遍历。

如何计算水量？这里算是按行计算，水量=水深×距离

由于相当于括号匹配，水量是按行自行填充的，你可以假设雨一直在下，没遇到匹配的那个柱子雨水就从右边漏掉了，遇到匹配的柱子就相当于堵住了可以计算之间的雨水量，所以不用担心形状不规则——它一定是成横行的，而且是高度模拟了下雨的过程（这里有个视频会更好理解）。

水的深度：新的栈顶对应的和当前位置的中较矮的那个减去刚出栈的。这句话非常抽象，人话来说就是围成的两个柱子较低的那个减去出栈的那个topV，因为更低洼的地方已经填充好雨水了。

距离：当前位置到刚出栈那个元素top的距离，由于提前出栈了，计算出的距离会更大，所以代码里是多减了个1。

代码

// 单调栈解法
// 执行耗时:24 ms,击败了11.83% 的Go用户
// 内存消耗:6 MB,击败了28.62% 的Go用户
func trapByStack(height []int) int {
   stack := make([]int, 1, len(height)) // 切片模拟单调栈，st存储的是高度数组下标
   sum, current := 0, 0
   for current < len(height) {
      //若栈不空且当前高度大于栈顶高度
      for len(stack) != 0 && height[current] > height[stack[len(stack)-1]] {
         top := stack[len(stack)-1]   //出栈的元素
         stack = stack[:len(stack)-1] //出栈
         //判断当前栈是否为空
         if len(stack) != 0 {
            distance := current - stack[len(stack)-1] - 1                            //墙间距
            depth := min(height[current], height[stack[len(stack)-1]]) - height[top] //水量
            sum += distance * depth
         }
      }
      stack = append(stack, current) //当前的墙入栈
      current++                      //指针移动
   }
   return sum
}

总结

这篇文章通过四种方式分析解决了接雨水问题，而这个问题的关键还是在于如何求出那两个柱子里较矮的那个。

暴力解法是通过遍历获得了左右两边的最高那个，动态规划是预先找到每个位置的左右两边最高的，双指针没完全按照从左到右的顺序去一一遍历，而是从两边向中间靠拢，也只需要知道更小的那个柱子就行，单调栈的话更像是在模拟下雨的过程，保证栈内索引的高度是从底往上递减的，通过匹配柱子的方式接收雨水。

至于哪种方法更好，Leetcode的结果有一定的参考性，但不绝对。

• ← Previous Post
• Next Post →