This array was divided into 2 parts, and the boundary is the maximum number.(if the maximum number show twice or more times, just pick the first one)
we use the same algorithm to review the array twice, from left to right and from right to left.
before we meet the maximum number, as long as the height goes down, fill it with water, because we must encounter the other bar which is higher than any other. After we meet the maximum number, the fill algorithm fails.
But start again from right to left, it can calculate the water from the other side. and add them together, the answer is correct
class Solution(object): def trap(self, height): """ :type height: List[int] :rtype: int """ maxh=0 water=0 total=0 for i in range(0,len(height)): if height[i]<maxh: water+=(maxh-height[i]) if height[i]>maxh: maxh=height[i] total+=water water=0 maxh=0 water=0 for i in range(len(height)-1,-1,-1): if height[i]<maxh: water+=(maxh-height[i]) if height[i]>=maxh: maxh=height[i] total+=water water=0 return total