1 题目
42. 接雨水
2 思路
之前讲过,只要逐个找出每个点左右的最大值,即可得到可以接的雨水;维护左右两个指针,以及left_max
, right_max
,这篇文章是看到论坛里有个同学用Rust
求解该题,结果花了144ms
......
3 代码
impl Solution {
pub fn trap(height: Vec) -> i32 {
let len= height.len();
let mut left= 0;
let mut left_max = height[left];
let mut right= len - 1;
let mut right_max= height[right];
let mut res= 0;
while left < right {
ifheight[left] <= height[right]{
if height[left] >=left_max{
left_max = height[left];
}else{
res += left_max - height[left];
}
left += 1;
}else{
if height[right] >=right_max{
right_max = height[right];
}else{
res += right_max - height[right];
}
right -= 1;
}
}
return res
}
}
【双指针进阶-接雨水-Rust语言描述】
文章图片