# 【Day 29】接雨水
# 题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/trapping-rain-water 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
# 我的回答
https://github.com/leetcode-pp/91alg-1/issues/57#issuecomment-650851027
# 解法一
通过计算每一列 两边最高的柱子获取区间面积，然后去除掉自己的高度
# 时间复杂度 O(n^2) 正好两个循环
# 空间复杂度 O(1) 创建一个参数空间空间
var trap = function(height) {
let sum = 0;
for (let i = 1; i < height.length; i++) {
let leftMax = 0;
for (let j = i - 1; j >= 0; j--) {
if (height[j] > leftMax) leftMax = height[j];
}
let rightMax = 0;
for (let j = i + 1; j <= height.length; j++) {
if (height[j] > rightMax) rightMax = height[j];
}
let data = Math.min(leftMax, rightMax) - height[i];
sum += data > 0 ? data : 0;
}
return sum;
};
# 解法二
空间换时间处理下
# 时间复杂度 O(n) 2 个独立的循环 2n
# 空间复杂度 O(n) 创建 2 个长度为 n 的空间
var trap = function(height) {
let sum = 0;
let leftMax = 0;
let rightMax = [0];
for (let i = height.length - 1; i > 0; i--) {
rightMax[i] = Math.max(rightMax[i + 1] || 0, height[i]);
}
for (let i = 1; i < height.length; i++) {
leftMax = Math.max(leftMax, height[i]);
let data = Math.min(leftMax, rightMax[i]) - height[i];
sum += data > 0 ? data : 0;
}
return sum;
};
# 解法三
使用双指针优化下空间
# 时间复杂度 O(n) left 和 right 正好走完一个循环
# 空间复杂度 O(1) 创建 5 个常量空间
var trap = function(height) {
let sum = 0;
let leftMax = 0;
let rightMax = 0;
let left = 0;
let right = height.length - 1;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
sum += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
sum += rightMax - height[right];
}
right--;
}
}
return sum;
};
看懂题解才写出来 太难了
# 参考回答
# 前置知识
- 空间换时间
- 双指针
- 单调栈
# 双数组
# 思路
这是一道雨水收集的问题， 难度为
hard. 如图所示，让我们求下过雨之后最多可以积攒多少的水。如果采用暴力求解的话，思路应该是 height 数组依次求和，然后相加。
伪代码:
for (let i = 0; i < height.length; i++) { area += (h[i] - height[i]) * 1; // h为下雨之后的水位 }问题转化为求 h，那么 h[i]又等于
左右两侧柱子的最大值中的较小值，即h[i] = Math.min(左边柱子最大值, 右边柱子最大值)如上图那么 h 为 [0, 1, 1, 2, 2, 2 ,2, 3, 2, 2, 2, 1]
问题的关键在于求解
左边柱子最大值和右边柱子最大值, 我们其实可以用两个数组来表示leftMax,rightMax， 以 leftMax 为例，leftMax[i]代表 i 的左侧柱子的最大值，因此我们维护两个数组即可。# 关键点解析
- 建模
h[i] = Math.min(左边柱子最大值, 右边柱子最大值)(h 为下雨之后的水位)# 代码
代码支持 JavaScript，Python3，C++:
JavaScript Code:
/* * @lc app=leetcode id=42 lang=javascript * * [42] Trapping Rain Water * */ /** * @param {number[]} height * @return {number} */ var trap = function(height) { let max = 0; let volumn = 0; const leftMax = []; const rightMax = []; for (let i = 0; i < height.length; i++) { leftMax[i] = max = Math.max(height[i], max); } max = 0; for (let i = height.length - 1; i >= 0; i--) { rightMax[i] = max = Math.max(height[i], max); } for (let i = 0; i < height.length; i++) { volumn = volumn + Math.min(leftMax[i], rightMax[i]) - height[i]; } return volumn; };Python Code:
class Solution: def trap(self, heights: List[int]) -> int: n = len(heights) l, r = [0] * (n + 1), [0] * (n + 1) ans = 0 for i in range(1, len(heights) + 1): l[i] = max(l[i - 1], heights[i - 1]) for i in range(len(heights) - 1, 0, -1): r[i] = max(r[i + 1], heights[i]) for i in range(len(heights)): ans += max(0, min(l[i + 1], r[i]) - heights[i]) return ansC++ Code:
int trap(vector<int>& heights) { if(heights == null) return 0; int ans = 0; int size = heights.size(); vector<int> left_max(size), right_max(size); left_max[0] = heights[0]; for (int i = 1; i < size; i++) { left_max[i] = max(heights[i], left_max[i - 1]); } right_max[size - 1] = heights[size - 1]; for (int i = size - 2; i >= 0; i--) { right_max[i] = max(heights[i], right_max[i + 1]); } for (int i = 1; i < size - 1; i++) { ans += min(left_max[i], right_max[i]) - heights[i]; } return ans; }复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(N)$
# 双指针
# 思路
上面代码比较好理解，但是需要额外的 ${N} 的空间。从上面解法可以看出，我们实际上只关心左右两侧较小的那一个，并不需要两者都计算出来。具体来说：
- 如果 l[i + 1] < r[i] 那么 最终积水的高度由 i 的左侧最大值决定。
- 如果 l[i + 1] >= r[i] 那么 最终积水的高度由 i 的右侧最大值决定。
因此我们不必维护完整的两个数组，而是可以只进行一次遍历，同时维护左侧最大值和右侧最大值，使用常数变量完成即可。这是一个典型的双指针问题，
具体算法：
维护两个指针 left 和 right，分别指向头尾。
初始化左侧和右侧最高的高度都为 0。
比较 height[left] 和 height[right]
3.1 如果 height[left] < height[right]，只看 left 即可。
- 3.1.1 如果 height[left] < left_max， 则当前格子积水面积为(left_max - height[left])
- 3.1.2 否则无法积水，即积水面积为 0
3.2 左指针右移一位
3.3 如果 height[left] >= height[right]，只看 right 即可。
- 3.3.1 如果 height[right] < right_max， 则当前格子积水面积为(right_max - height[right])
- 3.3.2 否则无法积水，即积水面积为 0
3.4 右指针左移一位
# 代码
代码支持 Python3，C++:
class Solution: def trap(self, heights: List[int]) -> int: n = len(heights) l_max = r_max = 0 l, r = 0, n - 1 ans = 0 while l < r: if heights[l] < heights[r]: if heights[l] < l_max: ans += l_max - heights[l] else: l_max = heights[l] l += 1 else: if heights[r] < r_max: ans += r_max - heights[r] else: r_max = heights[r] r -= 1 return ansclass Solution { public: int trap(vector<int>& heights) { int left = 0, right = heights.size() - 1; int ans = 0; int left_max = 0, right_max = 0; while (left < right) { if (heights[left] < heights[right]) { heights[left] >= left_max ? (left_max = heights[left]) : ans += (left_max - heights[left]); ++left; } else { heights[right] >= right_max ? (right_max = heights[right]) : ans += (right_max - heights[right]); --right; } } return ans; } };复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(1)$
# 相关题目