力扣加加 - 努力做西湖区最好的算法题解
lucifer 的博客
Github
公众号
搜索文档…
introduction
第一章 - 算法专题
第二章 - 91 天学算法
第三章 - 精选题解
第四章 - 高频考题(简单)
第五章 - 高频考题(中等)
第六章 - 高频考题(困难)
LCP 20. 快速公交
LCP 21. 追逐游戏
Number Stream to Intervals
Triple-Inversion
Kth-Pair-Distance
Minimum-Light-Radius
Largest Equivalent Set of Pairs
Ticket-Order.md
Connected-Road-to-Destination
0004. 寻找两个正序数组的中位数
0023. 合并 K 个升序链表
0025. K 个一组翻转链表
0030. 串联所有单词的子串
0032. 最长有效括号
0042. 接雨水
0052. N 皇后 II
0057. 插入区间
0065. 有效数字
0084. 柱状图中最大的矩形
0085. 最大矩形
0087. 扰乱字符串
0124. 二叉树中的最大路径和
0128. 最长连续序列
0132. 分割回文串 II
0140. 单词拆分 II
0145. 二叉树的后序遍历
0146. LRU 缓存机制
0154. 寻找旋转排序数组中的最小值 II
0212. 单词搜索 II
0239. 滑动窗口最大值
0295. 数据流的中位数
0297. 二叉树的序列化与反序列化
0301. 删除无效的括号
0312. 戳气球
330. 按要求补齐数组
0335. 路径交叉
0460. LFU 缓存
0472. 连接词
0480. 滑动窗口中位数
0483. 最小好进制
0488. 祖玛游戏
0493. 翻转对
0664. 奇怪的打印机
0679. 24 点游戏
0715. Range 模块
0726. 原子的数量
0768. 最多能完成排序的块 II
0805. 数组的均值分割
0839. 相似字符串组
0887. 鸡蛋掉落
0895. 最大频率栈
0975. 奇偶跳
0995. K 连续位的最小翻转次数
1032. 字符流
1168. 水资源分配优化
1178. 猜字谜
1203. 项目管理
1255. 得分最高的单词集合
1345. 跳跃游戏 IV
1449. 数位成本和为目标值的最大数字
1494. 并行课程 II
1521. 找到最接近目标值的函数值
1526. 形成目标数组的子数组最少增加次数
1649. 通过指令创建有序数组
1671. 得到山形数组的最少删除次数
1707. 与数组中元素的最大异或值
1713. 得到子序列的最少操作次数
1723. 完成所有工作的最短时间
1787. 使所有区间的异或结果为零
1835. 所有数对按位与结果的异或和
1871. 跳跃游戏 VII
1872. 石子游戏 VIII
1883. 准时抵达会议现场的最小跳过休息次数
1970. 你能穿过矩阵的最后一天
2009. 使数组连续的最少操作数
2025. 分割数组的最多方案数
2030. 含特定字母的最小子序列
2102. 序列顺序查询
2209. 用地毯覆盖后的最少白色砖块
2281.sum-of-total-strength-of-wizards
2306. 公司命名
5254. 卖木头块
5999. 统计数组中好三元组数目
后序
由
GitBook
提供支持
0042. 接雨水
题目地址(42. 接雨水)
https://leetcode-cn.com/problems/trapping-rain-water/
题目描述
1
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
Copied!
42.trapping-rain-water-1
1
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 感谢 Marcos 贡献此图。
2
3
示例:
4
5
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
6
输出: 6
Copied!
前置知识
空间换时间
双指针
单调栈
公司
阿里
腾讯
百度
字节
双数组
思路
这是一道雨水收集的问题, 难度为
hard
. 如图所示,让我们求下过雨之后最多可以积攒多少的水。
如果采用暴力求解的话,思路应该是 height 数组依次求和,然后相加。
伪代码
1
for
(
let
i
=
0
;
i
<
height
.
length
;
i
++
)
{
2
area
+=
(
h
[
i
]
-
height
[
i
])
*
1
;
// h为下雨之后的水位
3
}
Copied!
问题转化为求 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 为下雨之后的水位)
代码
代码支持: JS, Python3, C++:
JS Code:
1
/*
2
* @lc app=leetcode id=42 lang=javascript
3
*
4
* [42] Trapping Rain Water
5
*
6
*/
7
/**
8
* @param {number[]} height
9
* @return {number}
10
*/
11
var
trap
=
function
(
height
)
{
12
let
max
=
0
;
13
let
volume
=
0
;
14
const
leftMax
=
[];
15
const
rightMax
=
[];
16
17
for
(
let
i
=
0
;
i
<
height
.
length
;
i
++
)
{
18
leftMax
[
i
]
=
max
=
Math
.
max
(
height
[
i
],
max
);
19
}
20
21
max
=
0
;
22
23
for
(
let
i
=
height
.
length
-
1
;
i
>=
0
;
i
--
)
{
24
rightMax
[
i
]
=
max
=
Math
.
max
(
height
[
i
],
max
);
25
}
26
27
for
(
let
i
=
0
;
i
<
height
.
length
;
i
++
)
{
28
volume
=
volume
+
Math
.
min
(
leftMax
[
i
],
rightMax
[
i
])
-
height
[
i
];
29
}
30
31
return
volume
;
32
};
Copied!
Python Code:
1
class
Solution
:
2
def
trap
(
self
,
heights
:
List
[
int
])
->
int
:
3
n
=
len
(
heights
)
4
l
,
r
=
[
0
]
*
n
,
[
0
]
*
n
5
ans
=
0
6
for
i
in
range
(
1
,
len
(
heights
)):
7
l
[
i
]
=
max
(
l
[
i
-
1
],
heights
[
i
-
1
])
8
for
i
in
range
(
len
(
heights
)
-
2
,
0
,
-
1
):
9
r
[
i
]
=
max
(
r
[
i
+
1
],
heights
[
i
+
1
])
10
for
i
in
range
(
len
(
heights
)):
11
ans
+=
max
(
0
,
min
(
l
[
i
],
r
[
i
])
-
heights
[
i
])
12
return
ans
Copied!
C++ Code:
1
int
trap
(
vector
<
int
>&
heights
)
2
{
3
if
(
heights
==
null
)
4
return
0
;
5
int
ans
=
0
;
6
int
size
=
heights
.
size
();
7
vector
<
int
>
left_max
(
size
),
right_max
(
size
);
8
left_max
[
0
]
=
heights
[
0
];
9
for
(
int
i
=
1
;
i
<
size
;
i
++
)
{
10
left_max
[
i
]
=
max
(
heights
[
i
],
left_max
[
i
-
1
]);
11
}
12
right_max
[
size
-
1
]
=
heights
[
size
-
1
];
13
for
(
int
i
=
size
-
2
;
i
>=
0
;
i
--
)
{
14
right_max
[
i
]
=
max
(
heights
[
i
],
right_max
[
i
+
1
]);
15
}
16
for
(
int
i
=
1
;
i
<
size
-
1
;
i
++
)
{
17
ans
+=
min
(
left_max
[
i
],
right_max
[
i
])
-
heights
[
i
];
18
}
19
return
ans
;
20
}
Copied!
复杂度分析
时间复杂度:$O(N)$
空间复杂度:$O(N)$
双指针
思路
上面代码比较好理解,但是需要额外的 N 的空间。从上面解法可以看出,我们实际上只关心左右两侧较小的那一个,并不需要两者都计算出来。具体来说:
如果 l[i + 1] < r[i] 那么 最终积水的高度由 i 的左侧最大值决定。
如果 l[i + 1] >= r[i] 那么 最终积水的高度由 i 的右侧最大值决定。
因此我们不必维护完整的两个数组,而是可以只进行一次遍历,同时维护左侧最大值和右侧最大值,使用常数变量完成即可。这是一个典型的双指针问题,
具体算法:
1.
维护两个指针 left 和 right,分别指向头尾。
2.
初始化左侧和右侧最高的高度都为 0。
3.
比较 height[left] 和 height[right]
3.1 如果 height[left] < height[right], 那么瓶颈在于 height[left],不需要考虑 height[right]
3.1.1 如果 height[left] < left_max, 则当前格子积水面积为(left_max - height[left]),否则无法积水,即积水面积为 0。也可将逻辑统一为盛水量为 max(0, left_max - height[left])
3.1.2 左指针右移一位。(其实就是左指针的位置的雨水量已经计算完成了,我们移动到下个位置用同样的方法计算)
3.2 否则 瓶颈在于 height[right],不需要考虑 height[left]
3.2.1 如果 height[right] < right_max, 则当前格子积水面积为(right_max - height[left]),否则无法积水,即积水面积为 0。也可将逻辑统一为盛水量为 max(0, right_max - height[right])
3.2.2 右指针右移一位。(其实就是右指针的位置的雨水量已经计算完成了,我们移动到下个位置用同样的方法计算)
代码
代码支持: Python, C++, Go, PHP:
Python Code:
1
class
Solution
:
2
def
trap
(
self
,
heights
:
List
[
int
])
->
int
:
3
n
=
len
(
heights
)
4
l_max
=
r_max
=
0
5
l
,
r
=
0
,
n
-
1
6
ans
=
0
7
while
l
<
r
:
8
if
heights
[
l
]
<
heights
[
r
]:
9
if
heights
[
l
]
<
l_max
:
10
ans
+=
l_max
-
heights
[
l
]
11
else
:
12
l_max
=
heights
[
l
]
13
l
+=
1
14
else
:
15
if
heights
[
r
]
<
r_max
:
16
ans
+=
r_max
-
heights
[
r
]
17
else
:
18
r_max
=
heights
[
r
]
19
r
-=
1
20
return
ans
Copied!
C++ Code:
1
class
Solution
{
2
public
:
3
int
trap
(
vector
<
int
>&
heights
)
4
{
5
int
left
=
0
,
right
=
heights
.
size
()
-
1
;
6
int
ans
=
0
;
7
int
left_max
=
0
,
right_max
=
0
;
8
while
(
left
<
right
)
{
9
if
(
heights
[
left
]
<
heights
[
right
])
{
10
heights
[
left
]
>=
left_max
?
(
left_max
=
heights
[
left
])
:
ans
+=
(
left_max
-
heights
[
left
]);
11
++
left
;
12
}
13
else
{
14
heights
[
right
]
>=
right_max
?
(
right_max
=
heights
[
right
])
:
ans
+=
(
right_max
-
heights
[
right
]);
15
--
right
;
16
}
17
}
18
return
ans
;
19
}
20
21
};
Copied!
Go Code:
1
func
trap
(
height
[]
int
)
int
{
2
if
len
(
height
)
==
0
{
3
return
0
4
}
5
6
l
,
r
:=
0
,
len
(
height
)
-
1
7
lMax
,
rMax
:=
height
[
l
],
height
[
r
]
8
ans
:=
0
9
for
l
<
r
{
10
if
height
[
l
]
<
height
[
r
]
{
11
if
height
[
l
]
<
lMax
{
12
ans
+=
lMax
-
height
[
l
]
13
}
else
{
14
lMax
=
height
[
l
]
15
}
16
l
++
17
}
else
{
18
if
height
[
r
]
<
rMax
{
19
ans
+=
rMax
-
height
[
r
]
20
}
else
{
21
rMax
=
height
[
r
]
22
}
23
r
--
24
}
25
}
26
return
ans
27
}
Copied!
PHP Code:
1
class
Solution
2
{
3
4
/**
5
* @param Integer[] $height
6
* @return Integer
7
*/
8
function
trap
(
$height
)
9
{
10
$n
=
count
(
$height
);
11
if
(
!
$n
)
return
0
;
12
13
$l
=
0
;
14
$l_max
=
$height
[
$l
];
15
$r
=
$n
-
1
;
16
$r_max
=
$height
[
$r
];
17
$ans
=
0
;
18
while
(
$l
<
$r
)
{
19
if
(
$height
[
$l
]
<
$height
[
$r
])
{
20
if
(
$height
[
$l
]
<
$l_max
)
$ans
+=
$l_max
-
$height
[
$l
];
21
else
$l_max
=
$height
[
$l
];
22
$l
++
;
23
}
else
{
24
if
(
$height
[
$r
]
<
$r_max
)
$ans
+=
$r_max
-
$height
[
$r
];
25
else
$r_max
=
$height
[
$r
];
26
$r
--
;
27
}
28
}
29
return
$ans
;
30
}
31
}
Copied!
复杂度分析
时间复杂度:$O(N)$
空间复杂度:$O(1)$
相关题目
84.largest-rectangle-in-histogram
更多题解可以访问我的 LeetCode 题解仓库:
https://github.com/azl397985856/leetcode
。 目前已经 37K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。
以前
0032. 最长有效括号
下一个
0052. N 皇后 II
最近更新
1yr ago
复制链接
内容
题目地址(42. 接雨水)
题目描述
前置知识
公司
双数组
思路
关键点解析
代码
双指针
思路
代码
相关题目