Description
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.length1 <= n <= 2 * 1040 <= 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 ∑_{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.
PythonJavaC++GoTypeScriptRustC#PHP
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
left = [height[0]] * n
right = [height[-1]] * n
for i in range(1, n):
left[i] = max(left[i - 1], height[i])
right[n - i - 1] = max(right[n - i], height[n - i - 1])
return sum(min(l, r) - h for l, r, h in zip(left, right, height))(code-box)
class Solution {
public int trap(int[] height) {
int n = height.length;
int[] left = new int[n];
int[] right = new int[n];
left[0] = height[0];
right[n - 1] = height[n - 1];
for (int i = 1; i < n; ++i) {
left[i] = Math.max(left[i - 1], height[i]);
right[n - i - 1] = Math.max(right[n - i], height[n - i - 1]);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += Math.min(left[i], right[i]) - height[i];
}
return ans;
}
}(code-box)
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int left[n], right[n];
left[0] = height[0];
right[n - 1] = height[n - 1];
for (int i = 1; i < n; ++i) {
left[i] = max(left[i - 1], height[i]);
right[n - i - 1] = max(right[n - i], height[n - i - 1]);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += min(left[i], right[i]) - height[i];
}
return ans;
}
};(code-box)
func trap(height []int) (ans int) {
n := len(height)
left := make([]int, n)
right := make([]int, n)
left[0], right[n-1] = height[0], height[n-1]
for i := 1; i < n; i++ {
left[i] = max(left[i-1], height[i])
right[n-i-1] = max(right[n-i], height[n-i-1])
}
for i, h := range height {
ans += min(left[i], right[i]) - h
}
return
}(code-box)
function trap(height: number[]): number {
const n = height.length;
const left: number[] = new Array(n).fill(height[0]);
const right: number[] = new Array(n).fill(height[n - 1]);
for (let i = 1; i < n; ++i) {
left[i] = Math.max(left[i - 1], height[i]);
right[n - i - 1] = Math.max(right[n - i], height[n - i - 1]);
}
let ans = 0;
for (let i = 0; i < n; ++i) {
ans += Math.min(left[i], right[i]) - height[i];
}
return ans;
}(code-box)
impl Solution {
#[allow(dead_code)]
pub fn trap(height: Vec<i32>) -> i32 {
let n = height.len();
let mut left: Vec<i32> = vec![0; n];
let mut right: Vec<i32> = vec![0; n];
left[0] = height[0];
right[n - 1] = height[n - 1];
// Initialize the left & right vector
for i in 1..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]);
}
let mut ans = 0;
// Calculate the ans
for i in 0..n {
ans += std::cmp::min(left[i], right[i]) - height[i];
}
ans
}
}(code-box)
public class Solution {
public int Trap(int[] height) {
int n = height.Length;
int[] left = new int[n];
int[] right = new int[n];
left[0] = height[0];
right[n - 1] = height[n - 1];
for (int i = 1; i < n; ++i) {
left[i] = Math.Max(left[i - 1], height[i]);
right[n - i - 1] = Math.Max(right[n - i], height[n - i - 1]);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += Math.Min(left[i], right[i]) - height[i];
}
return ans;
}
}(code-box)
class Solution {
/**
* @param integer[] $height
* @return integer
*/
function trap($height) {
$n = count($height);
if ($n == 0) {
return 0;
}
$left = 0;
$right = $n - 1;
$leftMax = 0;
$rightMax = 0;
$ans = 0;
while ($left < $right) {
if ($height[$left] < $height[$right]) {
if ($height[$left] > $leftMax) {
$leftMax = $height[$left];
} else {
$ans += $leftMax - $height[$left];
}
$left++;
} else {
if ($height[$right] > $rightMax) {
$rightMax = $height[$right];
} else {
$ans += $rightMax - $height[$right];
}
$right--;
}
}
return $ans;
}
}(code-box)
