42. 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.
Solution:
Sum water amount of each bin (width=1). Maintain a height of left and right seperately, which is like a one-side wall of partial container. Fix the higher one and add the water amount regard to the lower part.
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
left, right = 0, 0
start, end = 0, len(height)-1
result = 0
while start <= end:
if left<right:
if height[start]>=left:
left = height[start]
else:
result += left - height[start]
start += 1
else:
if height[end]>=right:
right = height[end]
else:
result += right - height[end]
end -= 1
return result
[leetcode] Trapping rain water
原文：http://www.cnblogs.com/chrisyao/p/5812199.html