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]
, return6
.
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.Thanks Marcos for contributing this image!
URL: https://leetcode.com/problems/trapping-rain-water/
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
maxseenright = 0
maxseenright_arr = [0]*len(height)
maxseenleft = 0
rainwater = 0
for i in range(len(height) - 1, -1, -1):
if height[i] > maxseenright:
maxseenright_arr[i] = height[i]
maxseenright = height[i]
else:
maxseenright_arr[i] = maxseenright
for i in range(0, len(height)):
rainwater = rainwater + max(min(maxseenright_arr[i], maxseenleft) - height[i],0)
if height[i] > maxseenleft:
maxseenleft = height[i]
return rainwater