English
42. Trapping Rain Water
Problem Statement
Given n
non-negative integers representing an elevation map where the width of each bar is 1
, compute how much water it can trap after raining.
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
Constraints:
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
Solution:
rs
impl Solution {
pub fn trap(height: Vec<i32>) -> i32 {
let (mut left, mut right) = (0, height.len() - 1);
let (mut left_max, mut right_max) = (0, 0);
let mut ans = 0;
// iterate from both sides to the middle
while left < right {
// if left is lower than right, then the water level depends on left
// else the water level depends on right
if height[left] < height[right] {
// if left height is higher than left_max, then update left_max
// else add the difference between left_max and left height to ans
if height[left] >= left_max {
left_max = height[left];
} else {
ans += left_max - height[left];
}
left += 1;
} else {
// if right height is higher than right_max, then update right_max
// else add the difference between right_max and right height to ans
if height[right] >= right_max {
right_max = height[right];
} else {
ans += right_max - height[right];
}
right -= 1;
}
}
ans
}
}
...