42.py

'''
 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.
'''

classSolution(object):
deftrap(self, height):
"""
 :type height: List[int]
 :rtype: int
 """
ifnotheight:
return0

left, right=0, len(height) -1
leftMax, rightMax=0, 0
result=0
whileleft<right:
ifheight[left] <height[right]:
ifheight[left] >leftMax:
leftMax=height[left]
else:
result+= (leftMax-height[left])
left+=1
else:
ifheight[right] >rightMax:
rightMax=height[right]
else:
result+= (rightMax-height[right])
right-=1

returnresult