传言字节面试爱问的「接雨水」怎么解？

2024-04-22办公

坊间传闻，字节面试超爱问「接雨水」算法题。

今天就带大家盘一盘这道经典算法题。如果觉得内容对你有帮助的话麻烦点个赞👍。

一、题目描述

给定 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 个单位的雨水（蓝色部分表示雨水）。

二、题目解析

我们按照行方向去接雨水。

接下来我们去寻找凹槽。

一个凹槽是由三个柱子围成的 。（这里为了描述方便，我们把高度为 0 的柱子也当成存在的柱子）

对于这个凹槽来说，它的左侧和底部是由栈中挑选出来的，右侧是由新添加的柱子决定的。

什么情况会出现凹槽呢？

一旦新添加的柱子高度大于栈顶元素，就有可能形成凹槽！

这个时候，栈顶元素是凹槽的底部，如果在栈中存在 栈顶元素之前的元素 ，那么栈顶元素之前的元素就是凹槽的左侧，此时添加的元素是凹槽的右侧。

这里之所以是说有可能，是因为柱子里面可能是两根高度一样的柱子，即使新添加的柱子高度都大于它们，也是无法构成凹槽，或者说构成了一个面积为 0 的凹槽。

如果 新添加的柱子高度小于栈顶元素 ，那么必然无法和当前的栈中元素构成一个凹槽， 因为这是一个单调栈，里面的元素越靠近栈顶越小，新添加的柱子高度都小于了栈顶元素，那必然小于里面其它的元素， 这种情况下，无法围成一个凹槽，我们就把当前的柱子加入到我们的栈中，让它和里面的柱子一起等待接下来的柱子。

如果 新添加的柱子高度等于栈顶元素 ，也是无法形成凹槽的，我们就把当前的柱子加入到我们的栈中，让它和里面的柱子一起等待接下来的柱子。

一旦形成了凹槽，我们去计算它的面积。

面积由高和宽决定。

凹槽的高度是由 min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度 来计算的。

凹槽的宽度是由 凹槽右边的下标 - 凹槽左边的下标 - 1（因为只求中间宽度） 来计算的。

计算完一个凹槽的面积之后，我们就把栈顶元素弹出，观察 剩下的那些栈中的元素能否和新添加的元素再构成一个新的凹槽 。

三、参考代码

# 登录 AlgoMooc 官网获取更多算法图解 # https://www.algomooc.com # 作者：程序员吴师兄 # 代码有看不懂的地方一定要私聊咨询吴师兄呀 # 接雨水（ LeetCode 42 ）:https://leetcode-cn.com/problems/trapping-rain-water/ classSolution: deftrap(self, height: List[int]) -> int: # 构建一个栈，用来存储对应的柱子的下标 # stack 存储的是下标而非高度 stack = list() # 一开始水的面积是 0 result = 0 # 获取数组的长度 n = len(height) # 从头开始遍历整个数组 for i, h in enumerate(height): # 如果栈为空，那么直接把当前索引加入到栈中 ifnot stack : # 把当前索引加入到栈中 stack.append(i) # 否则的话，栈里面是有值的，我们需要去判断此时的元素、栈顶元素、栈顶之前的元素能否形成一个凹槽 # 情况一：此时的元素小于栈顶元素，凹槽的右侧不存在，无法形成凹槽 elif height[i] < height[stack[-1]]: # 把当前索引加入到栈中 stack.append(i) # 情况二：此时的元素等于栈顶元素，也是无法形成凹槽 elif height[i] == height[stack[-1]]: # 把当前索引加入到栈中 stack.append(i) # 情况三：此时的的元素大于栈顶元素，有可能形成凹槽 # 注意是有可能形成，因为比如栈中的元素是 2 、2 ，此时的元素是 3，那么是无法形成凹槽的 else : # 由于栈中有可能存在多个元素，移除栈顶元素之后，剩下的元素和此时的元素也有可能形成凹槽 # 因此，我们需要不断的比较此时的元素和栈顶元素 # 此时的元素依旧大于栈顶元素时，我们去计算此时的凹槽面积 # 借助 while 循环来实现这个操作 while stack and height[i] > height[stack[-1]]: # 1、获取栈顶的下标，bottom 为凹槽的底部位置 bottom = stack[-1] # 将栈顶元素推出，去判断栈顶之前的元素是否存在，即凹槽的左侧是否存在 stack.pop() # 2、如果栈不为空，即栈中有元素，即凹槽的左侧存在 if stack : # 凹槽左侧的高度 height[stack[-1] 和凹槽右侧的高度 height[i] # 这两者的最小值减去凹槽底部的高度就是凹槽的高度 h = min(height[stack[-1]], height[i]) - height[bottom] # 凹槽的宽度等于凹槽右侧的下标值 i 减去凹槽左侧的下标值 stack.top 再减去 1 w = i - stack[-1] - 1 # 将计算的结果累加到最终的结果上去 result += h * w # 栈中和此时的元素可以形成栈的情况在上述 while 循环中都已经判断了 # 那么，此时栈中的元素必然不可能大于此时的元素，所以可以把此时的元素添加到栈中 stack.append(i) # 最后返回结果即可 return result