算法题：接雨水
学习时间到，今天聊一个经典的算法问题：接雨水。
这是一个在面试中常常出现的题目，有时它考察的并不仅仅是你对算法的理解，还有你如何设计高效的解决方案。这个题目看似简单，但要写出一个高效的解法并不容易。我们先来看看题目的描述。
题目要求给定一个数组 height，数组的每个元素代表一个柱子的高度，柱子之间有空隙。雨水会被这些柱子围成坑，然后下雨的时候雨水会积在这些坑里。
我们的任务是计算这些坑中能够接到的雨水的总量。直白点说，就是你要计算数组中的“凹槽”，看看多少雨水会被这些“凹槽”接住。
你可能一开始就想到了暴力解法：对于每个柱子，去找它左边和右边最高的柱子，然后计算它可以接的雨水量。虽然这个思路是对的，但它的时间复杂度是 O(n^2)，显然这种方法在面对大数据量时就不太合适了。
我觉得，我们可以考虑优化这个问题，既然是求“凹槽”积水量，不妨从两头开始扫描，记录每一列可以接水的最大高度。具体来说，我们可以使用两个数组 left_max 和 right_max，分别记录每个位置左边和右边的最大高度。
算法的思路就像是你站在两个高楼之间，然后判断中间能接多少水。先扫描一遍得到左边的最高点，再扫描一遍得到右边的最高点，最后对于每个柱子来说，能够接的水量就是它左边和右边的最小高度减去它自己的高度。这样的话，水就能正确地分布在“坑”中。
看看这段代码实现，可能会对你理解这个问题有所帮助：
public class Solution {
public int trap(int[] height) {
if (height == null || height.length <= 2) {
return 0; // 小于三个柱子，不能接水
}
int n = height.length;
int[] left_max = new int[n];
int[] right_max = new int[n];
int water = 0;
// 初始化左侧最大高度
left_max[0] = height[0];
for (int i = 1; i < n; i++) {
left_max[i] = Math.max(left_max[i - 1], height[i]);
}
// 初始化右侧最大高度
right_max[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) {
right_max[i] = Math.max(right_max[i + 1], height[i]);
}
// 计算水量
for (int i = 0; i < n; i++) {
water += Math.min(left_max[i], right_max[i]) - height[i];
}
return water;
}
}
这个解法的时间复杂度是 O(n)，空间复杂度是 O(n)。通过这两个辅助数组，我们避免了暴力解法中的重复计算，能够更高效地求解接雨水的总量。
不过，这种方法虽然直观，但空间复杂度有点高。我们还能进一步优化，考虑到 left_max 和 right_max 数组的值只和当前元素及它们的左右邻居有关，所以我们可以将这两个数组压缩成两个变量，进一步将空间复杂度降低到 O(1)。来看下优化后的代码：
public class Solution {
public int trap(int[] height) {
if (height == null || height.length <= 2) {
return 0;
}
int left = 0, right = height.length - 1;
int left_max = 0, right_max = 0;
int water = 0;
while (left <= right) {
if (height[left] <= height[right]) {
if (height[left] >= left_max) {
left_max = height[left];
} else {
water += left_max - height[left];
}
left++;
} else {
if (height[right] >= right_max) {
right_max = height[right];
} else {
water += right_max - height[right];
}
right--;
}
}
return water;
}
}
这里我们使用了双指针的方法，left 从左往右遍历，right 从右往左遍历。每次根据左右两边的柱子高度，决定应该计算哪一边的积水量。这样空间复杂度就降到了 O(1)，而时间复杂度依然是 O(n)。
我觉得这个优化方法非常符合面试中常见的要求：你不仅要有一个正确的解法，还要有一个高效的解法。因为很多时候，面试官看中的是你的思维过程，而不是单纯的代码实现。
对编程、职场感兴趣的同学，可以链接我，微信：coder301 拉你进入“程序员交流群”。
