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
Solutions
Solution 1: Dynamic Programming
We define $left[i]$ as the height of the highest bar to the left of and including the position at index $i$, and $right[i]$ as the height of the highest bar to the right of and including the position at index $i$. Therefore, the amount of rainwater that can be trapped at index $i$ is $min(left[i], right[i]) - height[i]$. We traverse the array to calculate $left[i]$ and $right[i]$, and the final answer is $\sum_{i=0}^{n-1} \min(left[i], right[i]) - height[i]$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array.
implSolution{#[allow(dead_code)]pubfntrap(height:Vec<i32>)->i32{letn=height.len();letmutleft:Vec<i32>=vec![0;n];letmutright:Vec<i32>=vec![0;n];left[0]=height[0];right[n-1]=height[n-1];// Initialize the left & right vectorforiin1..n{left[i]=std::cmp::max(left[i-1],height[i]);right[n-i-1]=std::cmp::max(right[n-i],height[n-i-1]);}letmutans=0;// Calculate the ansforiin0..n{ans+=std::cmp::min(left[i],right[i])-height[i];}ans}}