题目描述
给定 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
难度:Middle
前置知识
- 空间换时间
- 双指针
- 单调栈
公司
- 阿里
- 腾讯
- 百度
- 字节
双数组
思路
这是一道雨水收集的问题, 难度为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:
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:前端中文网是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
* @lc app=leetcode id=42 lang=javascript
*
* [42] Trapping Rain Water
*
*/
/**
* @param {number[]} height
* @return {number}
*/
var trap = function (height) {
let max = 0;
let volume = 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++) {
volume = volume + Math.min(leftMax[i], rightMax[i]) - height[i];
}
return volume;
};
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 ans
C++ 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]
- 3.1.1 如果 height[left] >= left_max, 则当前格子积水面积为(left_max – height[left])
- 3.1.2 否则无法积水,即积水面积为 0
- 3.2 左指针右移一位
-
3.3 如果 height[left] >= height[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 ans
class 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)$
相关题目
更多题解可以访问我的 码农周刊 仓库:https://github.com/meibin08/free-programming-books, 一起学习更多前端前沿知识。
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com