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.
Test Cases
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
Solution
int trap(int* height, int n){
int left = 0, right = n-1;
int maxleft = 0, maxright = 0, total = 0;
while(left < right) {
if (height[left] < height[right]) {
if (height[left] < maxleft) {
total += maxleft - height[left];
} else {
maxleft = height[left];
}
left++;
} else {
if (height[right] < maxright) {
total += maxright - height[right];
} else {
maxright = height[right];
}
right--;
}
}
return total;
}class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int left = 0, right = n-1;
int maxleft = 0, maxright = 0, total = 0;
while(left < right) {
if (height[left] < height[right]) {
if (height[left] < maxleft) {
total += maxleft - height[left];
} else {
maxleft = height[left];
}
left++;
} else {
if (height[right] < maxright) {
total += maxright - height[right];
} else {
maxright = height[right];
}
right--;
}
}
return total;
}
};public class Solution {
public int Trap(int[] height) {
int left=0, right=height.Length-1, min, level=0, water=0;
while(left < right) {
if (height[left] < height[right]) {
min = height[left++];
} else {
min = height[right--];
}
if (min > level) level = min;
water += level - min;
}
return water;
}
}package trapping_rain_water
func trap(height []int) int {
n := len(height)
left, right := 0, n-1
maxLeft, maxRight, total := 0, 0, 0
for left < right {
if height[left] < height[right] {
if height[left] >= maxLeft {
maxLeft = height[left]
} else {
total += maxLeft - height[left]
}
left++
} else {
if height[right] >= maxRight {
maxRight = height[right]
} else {
total += maxRight - height[right]
}
right--
}
}
return total
}class Solution {
public int trap(int[] height) {
int n = height.length;
int left = 0, right = n-1;
int total = 0;
int maxLeft = 0, maxRight = 0;
while(left < right) {
if (height[left] < height[right]) {
if (height[left] >= maxLeft) {
maxLeft = height[left];
} else {
total += maxLeft - height[left];
}
left++;
} else {
if (height[right] >= maxRight) {
maxRight = height[right];
} else {
total += maxRight - height[right];
}
right--;
}
}
return total;
}
}/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
let left=0, right=height.length-1, min, level=0, water=0;
while(left < right) {
if (height[left] < height[right]) {
min = height[left++];
} else {
min = height[right--];
}
if (min > level) level = min;
water += level - min;
}
return water;
};from typing import List
class Solution:
def trap(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
maxleft, maxright, total = 0, 0, 0
while left < right:
if height[left] < height[right]:
if height[left] < maxleft:
total += maxleft - height[left]
else:
maxleft = height[left]
left += 1
else:
if height[right] < maxright:
total += maxright - height[right]
else:
maxright = height[right]
right -= 1
return total