-
Notifications
You must be signed in to change notification settings - Fork 11
Expand file tree
/
Copy pathTrappingRainWater.py
More file actions
57 lines (40 loc) · 1.22 KB
/
TrappingRainWater.py
File metadata and controls
57 lines (40 loc) · 1.22 KB
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# Trapping Rain Water
# Description
# Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
# Trapping Rain Water
# Example
# Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
# Challenge
# O(n) time and O(1) memory
# O(n) time and O(n) memory is also acceptable.
# Tags
# Two Pointers Forward-Backward Traversal Array
# Related Problems
# Medium Container With Most Water 40 %
# Hard Trapping Rain Water II 21 %
class Solution:
# @param heights: a list of integers
# @return: a integer
def trapRainWater(self, heights):
# write your code here
left = 0
right = len(heights) - 1
res = 0
if left >= right:
return res
leftH = heights[left]
rightH = heights[right]
while left < right:
if leftH < rightH:
left += 1
if leftH > heights[left]:
res += leftH - heights[left]
else:
leftH = heights[left]
else:
right -= 1
if rightH > heights[right]:
res += rightH = heights[right]
else:
rightH = heights[right]
return res