42. Trapping Rain Water
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.
avatar
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!
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
First
找到最大值辆雾，然后進行兩次遍歷
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
if not height: return 0
ans, tmp = 0, 0
max_height = (0, height[0])
for i, v in enumerate(height):
if v >= max_height[1]:
max_height = (i, v)
left = (0, height[0])
for i, v in enumerate(height[:max_height[0]+1]):
if v >= left[1]:
ans += (i-left[0]) * left[1] + tmp
left = (i, v)
tmp = 0
tmp -= v
tmp, left = 0, (0, height[-1])
sli = max_height[0] - len(height) - 1
print sli
for i, v in enumerate(height[-1:sli:-1]):
if v >= left[1]:
ans += (i-left[0]) * left[1] + tmp
left = (i, v)
tmp = 0
tmp -= v
return ans
s = Solution()
print s.trap([1,0,0,0,2,1,0,4,1,0,3])
print s.trap([4,2,3])
