#42
困难
高频
动态规划接雨水
这是一道围绕数组、图展开的高频练习。建议先掌握「动态规划」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
数组
图
题目分析
给你一组柱子的高度，宽度都视为 1。
下雨之后，问这些柱子之间总共能接住多少水。
一句话概括：
某个位置能接多少水，取决于它左边最高柱子和右边最高柱子里较矮的那个。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：预处理每个位置左侧最高柱和右侧最高柱，该位置能接的水量就是两者较小值减去当前高度。
推荐代码
推荐解法：动态规划
时间复杂度： O(n)
空间复杂度： O(n)
核心思路： 预处理每个位置左侧最高柱和右侧最高柱，该位置能接的水量就是两者较小值减去当前高度。
class Solution {
public int trap(int[] height) {
int n = height.length;
if (n == 0) {
return 0;
}
int[] leftMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; ++i) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
int[] rightMax = new int[n];
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; --i) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
}
}结构化讲解
面试时怎么讲
开场思路
这题我会先按列思考：每个位置能装多少水，再把它们加起来。
核心过程
- 先预处理每个位置左边和右边的最高柱子。
- 对于每一列，水位由左右最高柱中较低的那一个决定。
- 当前列的装水量就是这个水位减去自身高度。
- 把所有位置的装水量累加，就是总答案。
复杂度总结
时间复杂度 O(n)，空间复杂度 O(n)。
面试补一句：这题真正的核心句式是“单列水位由较低挡板决定”。
核心思路
接雨水的关键不是直接算总面积，而是看每个位置单独能装多少水。对某一列来说，装水上限由左右最高挡板中较低的那一个决定。
步骤讲解
1
预处理左侧最高柱
从左到右扫描，记录每个位置左边包含自身的最高柱子高度。
为什么这样做：每一列的装水高度上限必然受左边最高挡板影响。
对应代码提示：leftMax[i] = Math.max(leftMax[i - 1], height[i]);
2
预处理右侧最高柱
从右到左扫描，记录每个位置右边包含自身的最高柱子高度。
为什么这样做：另一侧挡板同样会限制该位置最终能盛多少水。
对应代码提示：rightMax[i] = Math.max(rightMax[i + 1], height[i]);
3
逐列计算可接雨水量
当前位置能装水的高度是 min(leftMax[i], rightMax[i]) - height[i]，把所有位置累加起来。
为什么这样做：较低挡板决定水位，当前柱子高度决定被占掉多少空间。
对应代码提示：answer += Math.min(leftMax[i], rightMax[i]) - height[i];
易错点
只看左右相邻柱子
真正决定水位的是左右两边的最高柱，而不是紧挨着的柱子。
正确理解：预处理的是到当前位置为止的左右最大值，不是局部相邻值。
先减高度再取 min
这样会破坏水位定义，得到错误结果。
正确理解：先算
min(leftMax, rightMax)，再减当前高度。边界位置也尝试装水
最左和最右没有两侧挡板，必然不能装水。
正确理解：即使统一计算，它们的结果也应为 0；理解上要明确边界不会存水。
复杂度与适用判断
时间复杂度：O(n)
空间复杂度：O(n)
比其他方案更好在哪里：比暴力向左右搜索最高柱的
O(n^2) 写法高效，也比双指针版本更容易初次解释。适用判断：如果题目要求按位置计算局部贡献，且局部值依赖左右全局信息，优先考虑预处理数组。
额外提醒
- 先把问题拆成“每一列能装多少”，会比直接看总面积更清楚。
其他语言 / 其他解法
栈
单调栈解法：
- 使用单调栈存储柱子的索引，保持栈内柱子高度递减
- 当遇到比栈顶柱子高的柱子时，弹出栈顶元素作为凹槽底部
- 计算凹槽的宽度和高度，进而得到该凹槽能接的雨水量
- 遍历完成后，所有凹槽的雨水量之和即为总接水量
栈
单调栈解法：
时间复杂度：O(n)
空间复杂度：O(n)
一句话思路：单调栈解法：
- 使用单调栈存储柱子的索引，保持栈内柱子高度递减
- 当遇到比栈顶柱子高的柱子时，弹出栈顶元素作为凹槽底部
- 计算凹槽的宽度和高度，进而得到该凹槽能接的雨水量
- 遍历完成后，所有凹槽的雨水量之和即为总接水量
class Solution {
public int trap(int[] height) {
int ans = 0;
Deque<Integer> stack = new LinkedList<Integer>();
int n = height.length;
for (int i = 0; i < n; ++i) {
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int top = stack.pop();
if (stack.isEmpty()) {
break;
}
int left = stack.peek();
int currWidth = i - left - 1;
int currHeight = Math.min(height[left], height[i]) - height[top];
ans += currWidth * currHeight;
}
stack.push(i);
}
return ans;
}
}动画演示
如果你还没完全看懂，可以展开动画演示。
动态规划动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
动态规划动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
动态规划 - 接雨水
总接水量: 0
柱子高度
左侧最大值
右侧最大值
接水量
栈动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
栈动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
单调栈 - 接雨水
单调栈状态:
空
步骤信息:
初始化，准备开始处理柱子
总接水量: 0
普通柱子
栈中柱子
接水量
当前处理
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。