```
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
n = len(height)
if n == 0:
return 0
total = 0
# in order to fullfill O(n), we first record the max of left part and right part at each position
max_left, max_right = [0]*n, [0]*n # we would like max_left[i]=max(height[:i+1]) and max_right[i]=max(height[i:])
max_left[0], max_right[n-1] = height[0], height[n-1]
# traverse the list and fill max_left and max_right
for i in range(1, n, 1):
max_left[i], max_right[n-1-i] = max(height[i], max_left[i-1]), max(height[n-1-i], max_right[n-i])
# traverse the list and accumulate water at each position
for i in range(n):
total += min(max_left[i], max_right[i]) - height[i]
return total
```