从"原神"出知名题，谈面试最佳实践
写在前面
这是一道经典到几乎每个人（刷题量超过 200）都见过的 Hard 题。
即使在算法内卷到"网络流"都会考的今年，也还是各大互联网的最爱（或是面试官脑内题库没有更新 🤣
据同学们反映，在 抖音提前批一面、拼多多二面 以及 字节跳动 飞书三面 遇到过。
而在最新的公众号投稿留言中，则是提到 米哈游 近期考到了。
虽然是经典 Hard，但由于解法繁多，想要 100% 答到面试官的"点"上，还是需要有所积累的。
对于本题，我准备了四种解法，可以说覆盖了本题的所有求解方式。
思维难度也是"由浅到深"，下面请大家一起看看（欢迎评论区告诉我，你撑到的是第几关
在开始之前，提醒一下：无论在第几关倒下，都记得去看 文末彩蛋，你会发价值远比四种解法要高（但如果你现在就准备滑到最后去看，那不是我的本意，收起你的小聪明 🤣
题目描述
来源：LeetCode
题号：42
给定 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
提示：
- n=height.lengthn = height.lengthn=height.length
- 0<=n<=2×1040 <= n <= 2 \times 10^40<=n<=2×104
- 0<=height[i]<=1050 <= height[i] <= 10^50<=height[i]<=105
模拟
对每根柱子而言，我们先找出其「左边最高的柱子」和「右边最高的柱子」。
对左右最高柱子取较小值，再和当前柱子高度做比较，即可得出当前位置可以接下的雨水。
同时，边缘的柱子不可能接到雨水（某一侧没有柱子）。
最后注意：该解法计算量会去到 n2=4×108n^2 = 4 \times 10^8n2=4×108，一旦计算量上界接近 10710^7107，我们就需要考虑 TLE（超时）问题，在 LeetCode 上该解法 C++ 无法通过，其他语言目前还能通过。
Java 代码：
class Solution {
public int trap(int[] height) {
int n = height.length;
int ans = 0;
for (int i = 1; i < n - 1; i++) {
int cur = height[i];
// 获取当前位置的左边最大值
int l = Integer.MIN_VALUE;
for (int j = i - 1; j >= 0; j--) l = Math.max(l, height[j]);
if (l <= cur) continue;
// 获取当前位置的右边边最大值
int r = Integer.MIN_VALUE;
for (int j = i + 1; j < n; j++) r = Math.max(r, height[j]);
if (r <= cur) continue;
// 计算当前位置可接的雨水
ans += Math.min(l, r) - cur;
}
return ans;
}
}
C++ 代码：
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int ans = 0;
for (int i = 1; i < n - 1; i++) {
int cur = height[i];
// 获取当前位置的左边最大值
int l = INT_MIN;
for (int j = i - 1; j >= 0; j--) l = max(l, height[j]);
if (l <= cur) continue;
// 获取当前位置的右边边最大值
int r = INT_MIN;
for (int j = i + 1; j < n; j++) r = max(r, height[j]);
if (r <= cur) continue;
// 计算当前位置可接的雨水
ans += min(l, r) - cur;
}
return ans;
}
};
Python 代码：
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
ans = 0
for i in range(1, n - 1):
cur = height[i]
# 获取当前位置的左边最大值
l = max(height[:i])
if l <= cur: continue
# 获取当前位置的右边最大值
r = max(height[i + 1:])
if r <= cur: continue
# 计算当前位置可接的雨水
ans += min(l, r) - cur
return ans
TypeScript 代码：
function trap(height: number[]): number {
const n = height.length;
let ans = 0;
for (let i = 1; i < n - 1; i++) {
const cur = height[i];
// 获取当前位置的左边最大值
const l = Math.max(...height.slice(0, i));
if (l <= cur) continue;
// 获取当前位置的右边最大值
const r = Math.max(...height.slice(i + 1));
if (r <= cur) continue;
// 计算当前位置可接的雨水
ans += Math.min(l, r) - cur;
}
return ans;
};
- 时间复杂度：需要处理所有非边缘的柱子，复杂度为 O(n)O(n)O(n)；对于每根柱子而言，需要往两边扫描分别找到最大值，复杂度为 O(n)O(n)O(n)。整体复杂度为 O(n2)O(n^2)O(n2)
- 空间复杂度：O(1)O(1)O(1)
预处理最值
朴素解法的思路有了，我们想想怎么优化。
事实上，任何的优化无非都是「减少重复」。
想想在朴素思路中有哪些环节比较耗时，耗时环节中又有哪些地方是重复的，可以优化的。
首先对每根柱子进行遍历，求解每根柱子可以接下多少雨水，这个 O(n)O(n)O(n) 操作肯定省不了。
在求解某根柱子可以接下多少雨水时，需要对两边进行扫描，求两侧的最大值。
每一根柱子都进行这样的扫描操作，导致每个位置都被扫描了 nnn 次。这个过程显然是可优化的。
换句话说：我们希望通过不重复遍历的方式找到任意位置的两侧最大值。
问题转化为：给定一个数组，如何求得任意位置的左半边的最大值和右半边的最大值。
一个很直观的方案：直接将某个位置的两侧最大值存起来。
我们可以先从两端分别出发，预处理每个位置的「左右最值」，这样可以将我们「查找左右最值」的复杂度降到 O(1)O(1)O(1)。
整体算法的复杂度也从 O(n2)O(n^2)O(n2) 下降到 O(n)O(n)O(n)。
Java 代码：
class Solution {
public int trap(int[] height) {
int n = height.length;
int ans = 0;
// 由于预处理最值的时候，我们会直接访问到 height[0] 或者 height[n - 1]，因此要特判一下
if (n == 0) return ans;
// 预处理每个位置左边的最值
int[] lm = new int[n];
lm[0] = height[0];
for (int i = 1; i < n; i++) lm[i] = Math.max(height[i], lm[i - 1]);
// 预处理每个位置右边的最值
int[] rm = new int[n];
rm[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) rm[i] = Math.max(height[i], rm[i + 1]);
for (int i = 1; i < n - 1; i++) {
int cur = height[i], l = lm[i], r = rm[i];
if (l <= cur || r <= cur) continue;
ans += Math.min(l, r) - cur;
}
return ans;
}
}
C++ 代码：
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size(), ans = 0;
// 由于预处理最值的时候，我们会直接访问到 height[0] 或者 height[n - 1]，因此要特判一下
if (n == 0) return ans;
vector<int> lm(n, 0), rm(n, 0);
// 预处理每个位置左边的最值
lm[0] = height[0];
for (int i = 1; i < n; i++) lm[i] = max(height[i], lm[i - 1]);
// 预处理每个位置右边的最值
rm[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) rm[i] = max(height[i], rm[i + 1]);
for (int i = 1; i < n - 1; i++) {
int cur = height[i], l = lm[i], r = rm[i];
if (l <= cur || r <= cur) continue;
ans += min(l, r) - cur;
}
return ans;
}
};
Python 代码：
class Solution:
def trap(self, height: List[int]) -> int:
n, ans = len(height), 0
# 由于预处理最值的时候，我们会直接访问到 height[0] 或者 height[n - 1]，因此要特判一下
if n == 0: return ans
lm, rm = [0] * n, [0] * n
# 预处理每个位置左边的最值
lm[0] = height[0]
for i in range(1, n):
lm[i] = max(height[i], lm[i - 1])
# 预处理每个位置右边的最值
rm[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1):
rm[i] = max(height[i], rm[i + 1])
for i in range(1, n - 1):
cur, l, r = height[i], lm[i], rm[i]
if l <= cur or r <= cur: continue
ans += min(l, r) - cur
return ans
TypeScript 代码：
function trap(height: number[]): number {
let n = height.length, ans = 0;
// 由于预处理最值的时候，我们会直接访问到 height[0] 或者 height[n - 1]，因此要特判一下
if (n == 0) return ans;
const lm = new Array(n).fill(0), rm = new Array(n).fill(0);
// 预处理每个位置左边的最值
lm[0] = height[0];
for (let i = 1; i < n; i++) lm[i] = Math.max(height[i], lm[i - 1]);
// 预处理每个位置右边的最值
rm[n - 1] = height[n - 1];
for (let i = n - 2; i >= 0; i--) rm[i] = Math.max(height[i], rm[i + 1]);
for (let i = 1; i < n - 1; i++) {
const cur = height[i], l = lm[i], r = rm[i];
if (l <= cur || r <= cur) continue;
ans += Math.min(l, r) - cur;
}
return ans;
};
- 时间复杂度：预处理出两个最大值数组，复杂度为 O(n)O(n)O(n)；计算每根柱子可接的雨水量，复杂度为 O(n)O(n)O(n)。整体复杂度为 O(n)O(n)O(n)
- 空间复杂度：使用了数组存储两侧最大值。复杂度为 O(n)O(n)O(n)
单调栈
前面我们讲到，优化思路将问题转化为：给定一个数组，如何求得任意位置的左半边的最大值和右半边的最大值。
但仔细一想，其实我们并不需要找两侧最大值，只需要找到两侧最近的比当前位置高的柱子就行了。
针对这一类找最近值的问题，有一个通用解法：单调栈。
单调栈其实就是在栈的基础上，维持一个栈内元素单调。
在这道题，由于需要找某个位置两侧比其高的柱子（只有两侧有比当前位置高的柱子，当前位置才能接下雨水），我们可以维持栈内元素的单调递减。
PS. 找某侧最近一个比其大的值，使用单调栈维持栈内元素递减；找某侧最近一个比其小的值，使用单调栈维持栈内元素递增 ...
当某个位置的元素弹出栈时，例如位置 a ，我们自然可以得到 a 位置两侧比 a 高的柱子：
- 一个是导致
a位置元素弹出的柱子（a右侧比a高的柱子） - 一个是
a弹栈后的栈顶元素（a左侧比a高的柱子）
当有了 a 左右两侧比 a 高的柱子后，便可计算 a 位置可接下的雨水量。
Java 代码：
class Solution {
public int trap(int[] height) {
int n = height.length, ans = 0;
Deque<Integer> d = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!d.isEmpty() && height[i] > height[d.peekLast()]) {
int cur = d.pollLast();
// 如果栈内没有元素，说明当前位置左边没有比其高的柱子，跳过
if (d.isEmpty()) continue;
// 左右位置，并由左右位置得出「宽度」和「高度」
int l = d.peekLast(), r = i;
int w = r - l + 1 - 2, h = Math.min(height[l], height[r]) - height[cur];
ans += w * h;
}
d.addLast(i);
}
return ans;
}
}
C++ 代码：
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size(), ans = 0;
deque<int> d;
for (int i = 0; i < n; i++) {
while (!d.empty() && height[i] > height[d.back()]) {
int cur = d.back();
d.pop_back();
// 如果栈内没有元素，说明当前位置左边没有比其高的柱子，跳过
if (d.empty()) continue;
// 左右位置，并由左右位置得出「宽度」和「高度」
int l = d.back(), r = i;
int w = r - l + 1 - 2, h = min(height[l], height[r]) - height[cur];
ans += w * h;
}
d.push_back(i);
}
return ans;
}
};
Python 代码：
class Solution:
def trap(self, height: List[int]) -> int:
n, ans = len(height), 0
d = deque()
for i in range(n):
while d and height[i] > height[d[-1]]:
cur = d.pop()
# 如果栈内没有元素，说明当前位置左边没有比其高的柱子，跳过
if not d: continue
# 左右位置，并由左右位置得出「宽度」和「高度」
l, r = d[-1], i
w, h = r - l + 1 - 2, min(height[l], height[r]) - height[cur]
ans += w * h
d.append(i)
return ans
TypeScript 代码：
function trap(height: number[]): number {
let n = height.length, ans = 0;
const d = [];
for (let i = 0; i < n; i++) {
while (d.length && height[i] > height[d[d.length - 1]]) {
const cur = d.pop() as number;
// 如果栈内没有元素，说明当前位置左边没有比其高的柱子，跳过
if (!d.length) continue;
// 左右位置，并由左右位置得出「宽度」和「高度」
const l = d[d.length - 1], r = i;
const w = r - l + 1 - 2, h = Math.min(height[l], height[r]) - height[cur];
ans += w * h;
}
d.push(i);
}
return ans;
};
- 时间复杂度：每个元素最多进栈和出栈一次。复杂度为 O(n)O(n)O(n)
- 空间复杂度：栈最多存储 nnn 个元素。复杂度为 O(n)O(n)O(n)
面积差值
事实上，我们还能利用「面积差值」来进行求解。
我们先统计出「柱子面积」sumsumsum 和「以柱子个数为宽、最高柱子高度为高的矩形面积」fullfullfull。
然后分别「从左往右」和「从右往左」计算一次最大高度覆盖面积 lSumlSumlSum 和 rSumrSumrSum。
显然会出现重复面积，并且重复面积只会独立地出现在「山峰」的左边和右边。
利用此特性，我们可以通过简单的等式关系求解出「雨水面积」：
Java 代码：
class Solution {
public int trap(int[] height) {
int n = height.length;
int sum = 0, max = 0;
for (int i = 0; i < n; i++) {
int cur = height[i];
sum += cur;
max = Math.max(max, cur);
}
int full = max * n;
int lSum = 0, lMax = 0;
for (int i = 0; i < n; i++) {
lMax = Math.max(lMax, height[i]);
lSum += lMax;
}
int rSum = 0, rMax = 0;
for (int i = n - 1; i >= 0; i--) {
rMax = Math.max(rMax, height[i]);
rSum += rMax;
}
return lSum + rSum - full - sum;
}
}
C++ 代码：
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int sum = 0, maxv = 0;
for (int i = 0; i < n; i++) {
int cur = height[i] * 1L;
sum += cur;
maxv = max(maxv, cur);
}
int full = maxv * n;
int lSum = 0, lMax = 0;
for (int i = 0; i < n; i++) {
lMax = max(lMax, height[i]);
lSum += lMax;
}
int rSum = 0, rMax = 0;
for (int i = n - 1; i >= 0; i--) {
rMax = max(rMax, height[i]);
rSum += rMax;
}
return lSum - full - sum + rSum; // 考虑到 C++ 溢出报错, 先减后加
}
};
Python 代码：
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
sum_val, max_val = 0, 0
for cur in height:
sum_val += cur
max_val = max(max_val, cur)
full = max_val * n
l_sum, l_max = 0, 0
for h in height:
l_max = max(l_max, h)
l_sum += l_max
r_sum, r_max = 0, 0
for i in range(n - 1, -1, -1):
r_max = max(r_max, height[i])
r_sum += r_max
return l_sum + r_sum - full - sum_val
TypeScript 代码：
function trap(height: number[]): number {
const n = height.length;
let sum = 0, max = 0;
for (let i = 0; i < n; i++) {
const cur = height[i];
sum += cur;
max = Math.max(max, cur);
}
const full = max * n;
let lSum = 0, lMax = 0;
for (let i = 0; i < n; i++) {
lMax = Math.max(lMax, height[i]);
lSum += lMax;
}
let rSum = 0, rMax = 0;
for (let i = n - 1; i >= 0; i--) {
rMax = Math.max(rMax, height[i]);
rSum += rMax;
}
return lSum + rSum - full - sum;
};
- 时间复杂度：O(n)O(n)O(n)
- 空间复杂度：O(1)O(1)O(1)
面试最佳实践
其实这道 "经典" 而又 "解法繁多" 的高频 Hard 题，还向大家揭露了一个残忍的现实：
互联网面试中，算法除了作为考察点以外，一定程度还能为面试提供"灵活度"。
这样说可能大家没有概念，用两个对比例子，大家就能理解。
例如，拙劣的"灵活度"：
高端的"灵活度"，统一考「接雨水」这道题：
- 要你：「能回答出处理"预处理法"就行，实在不行，朴素的"模拟"解法写得清晰也可以」
- 不要你：「会"单调栈"又怎么样？我要的是"面积差法"」
如果现实就是如此残忍，那么有什么东西或方法，可以指导我们做得更好？
当然是你四种解法都掌握了，并且能以"由浅入深"地解释给面试官听。
在这个过程中，不但摧毁了面试官试图从"灵活度"来否决你的"小聪明"。
还有可能让 ta 对你有所改观，重新拿回面试过程的主动性。
这是最好的 "将陷阱变馅饼" 的方式。
而且在面试中，一旦遇到了这种，有较多你熟悉的东西可以表达的时刻。
应当将这个过程，以「缓和、有条理、不结巴」的方式逐步推进。
这并不是单纯为了将战线拉长。
你要知道一场面试下来，可能面试官比你还累。
但我们仍然需要在某些时刻，将“沟通”适当的拉长。
这其实是一个心理学的 trick：人的理解和共情，就是要有足够的「篇幅」才能产生的。
面试过程中，面试官对你的认可，一定程度也是一种"理解和共情"。
举个例子吧。
在一部电影里，A 和 B 进行比赛，此时如果以 A 的第一人称视角播放一段剧情，到最后我们会希望 A 赢得比赛；反过来，如果是先以 B 的第一人称视角播放一段剧情，我们则希望 B 赢。
这就是因为前面那一段第一人称视角，使得我们与 A 或 B 产生了共情作用。
那么对应的，如果面试被问到「接雨水」，我们应当将四种解法，逐步地 缓慢地 回答出来。
只要面试官的倾听过程达到一定「篇幅」，那么他就会和你产生共情作用，从而转化为对你的认可。
难怕他原本对这四种解法都十分了解，也会对你产生深深的共情作用，因为人脑的杏仁体就是被这样设计的。
可能到面试结束，他甚至都忘记了你的四种解法是什么，但是他仍然会带着对你深深的认同感，在评分一栏打下高分。
再次强调，因为人脑的杏仁体就是被这样设计的。
好，我已经向你介绍完，如果在面试中遇到「接雨水」，最佳实践的轮廓是什么。
推而广之，在任何面试沟通过程中，你都可以运用这种 trick，但需要注意合适的度。
面试中任何环节，都应当有明确分值上界。
在某个具体的问题上，就算答上一个小时，答出花来，也只是局部"满分"。
因此无底线地将回答延长，不是我们所推崇的。
那么一个科学的，能够产生共情的"篇幅"大小是多少呢？
大概是 22 到 35 分钟，极限是 45 分钟。
将"篇幅"控制在这个时长，既能达到产生共情的作用，又不显得你啰嗦，无节制。
至此，我将关于「最佳实践」的所有细节都告诉你了。
最后，如果你真的是直接从文章头部滑到这里看总结的"小聪明鬼"，那么我还是要提醒你，本文的重点是在于对经典 Hard「接雨水」的四种解法，只有全部掌握，你才具备使用这类面试技巧的前提。
下期见。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉