42. 接雨水
查看题目困难
数组
图
高频
解法一：动态规划
时间复杂度：O(n) | 空间复杂度：O(n) | 推荐使用
动画演示
动态规划 - 接雨水
总接水量: 0
柱子高度
左侧最大值
右侧最大值
接水量
代码实现
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数组中
2. 计算每个位置右边的最大高度，存储在rightMax数组中
3. 遍历数组，每个位置能接的雨水量等于min(leftMax[i], rightMax[i]) - height[i]
4. 将所有位置的雨水量相加，得到总接水量
解法二：栈
时间复杂度：O(n) | 空间复杂度：O(n)
动画演示
单调栈 - 接雨水
单调栈状态:
空
步骤信息:
初始化，准备开始处理柱子
总接水量: 0
普通柱子
栈中柱子
接水量
当前处理
代码实现
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;
}
}时间复杂度：O(n)
空间复杂度：O(n)
单调栈解法：
1. 使用单调栈存储柱子的索引，保持栈内柱子高度递减
2. 当遇到比栈顶柱子高的柱子时，弹出栈顶元素作为凹槽底部
3. 计算凹槽的宽度和高度，进而得到该凹槽能接的雨水量
4. 遍历完成后，所有凹槽的雨水量之和即为总接水量