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.length0 <= n <= 3 * 1040 <= height[i] <= 105
Two pointers from both sides, and record the max from both sides
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
def trap(self, height: List[int]) -> int:
res = 0
l, r = 0, len(height) - 1
max_l, max_r = -1, -1
while l <= r:
if height[l] <= height[r]:
if height[l] > max_l:
max_l = height[l]
else:
res += max_l - height[l]
l += 1
else:
if height[r] > max_r:
max_r = height[r]
else:
res += max_r - height[r]
r -= 1
return res
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
func trap(height []int) int {
n := len(height)
left := 0
right := n - 1
res := 0
maxLeft := 0
maxRight := 0
for left <= right {
if height[left] <= height[right] {
if height[left] > maxLeft {
maxLeft = height[left]
} else {
res += maxLeft - height[left]
}
left++
} else {
if height[right] >= maxRight {
maxRight = height[right]
} else {
res += maxRight - height[right]
}
right--
}
}
return res
}
|