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.
For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
The above elevation map 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.
Python Solution 1:
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
if len(height) < 3: return 0
l, r = height[:], height[:]
for i in range(1, len(height)):
l[i] = max(l[i - 1], l[i])
j = len(height) - 1 - i
r[j] = max(r[j + 1], height[j])
return sum(min(l[i], r[i]) - height[i] for i in range(len(height)))
Python Solution 2:
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
stack = []
res = 0
for i, cur in enumerate(height):
while stack and cur > stack[-1][0]:
pop = stack.pop()
if not stack: break
res += (min(stack[-1][0], cur) - pop[0]) * (i - stack[-1][1] - 1)
stack.append((cur, i))
return res
Python Solution 3:
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
lb, rb = 0, len(height) - 1
l, r = 1, len(height) - 2
res = 0
while l <= r:
if height[lb] < height[rb]:
if height[l] > height[lb]:
lb = l
else:
res += height[lb] - height[l]
l += 1
else:
if height[r] > height[rb]:
rb = r
else:
res += height[rb] - height[r]
r -= 1
return res
Summary:
- beautiful.
LeetCode: 42. Trapping Rain Water
近期评论