接雨水问题大厂面试高频解析：算法核心与实战技巧
在算法面试中，LeetCode 42号题"接雨水"是字节跳动、腾讯等公司的常客，出现概率高达70%。本题要求计算一组非负整数代表柱子高度图所能承接的雨水量。
示例：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：柱子之间凹陷区域可以存储雨水。
难度：中等偏难 | 面试频率：字节跳动（高）、腾讯（高）、阿里巴巴（中高）
算法解析：从"接水"到"边界"的思维突破
核心在于转换问题视角：不要关注水本身，而是关注每个位置的左右两侧边界。
解法一：动态规划（推荐）
通过预处理每个柱子的左右最大边界值，降低计算复杂度。
public int trapWater(int[] heights) {
int n = heights.length;
if (n == 0) return 0;
int[] leftBoundary = new int[n];
int[] rightBoundary = new int[n];
leftBoundary[0] = heights[0];
for (int i = 1; i < n; i++) {
leftBoundary[i] = Math.max(leftBoundary[i-1], heights[i]);
}
rightBoundary[n-1] = heights[n-1];
for (int i = n-2; i >= 0; i--) {
rightBoundary[i] = Math.max(rightBoundary[i+1], heights[i]);
}
int totalWater = 0;
for (int i = 0; i < n; i++) {
totalWater += Math.min(leftBoundary[i], rightBoundary[i]) - heights[i];
}
return totalWater;
}
时间复杂度：O(n) | 空间复杂度：O(n)
解法二：双指针（空间优化）
通过左右指针动态跟踪边界，无需额外数组。
public int trapWater(int[] heights) {
int left = 0, right = heights.length - 1;
int leftMax = 0, rightMax = 0;
int total = 0;
while (left < right) {
if (heights[left] < heights[right]) {
if (heights[left] >= leftMax) {
leftMax = heights[left];
} else {
total += leftMax - heights[left];
}
left++;
} else {
if (heights[right] >= rightMax) {
rightMax = heights[right];
} else {
total += rightMax - heights[right];
}
right--;
}
}
return total;
}
时间复杂度：O(n) | 空间复杂度：O(1) - 极致优化
解题方法论核心
- 问题转化：将"接水"抽象为"边界计算"
- 预处理思维：用空间换时间，降低时间复杂度
- 双指针策略：左右夹击，动态更新边界
- 木桶原理：水位由最短边界决定
"不要被题目表象迷惑，找到问题的本质特征"
面试扩展题型
- 三维接雨水（LeetCode 407题）：升级到三维空间，需使用最小堆
- 盛最多水的容器（LeetCode 11题）：类似双指针应用，但计算逻辑不同
- 柱状图中最大矩形（LeetCode 84题）：柱状图变体，使用单调栈解决
学习路径建议
基础先行：掌握数组、链表、树、图等基本数据结构。
思维训练：精练100道核心高频题。
实战演练：参与模拟面试提升应变能力。
