# Share my python solution

• ``````class Solution:
# @param {integer[]} height
# @return {integer}
def trap(self, height):
if not height:
return 0

s = []
water_vol = 0
for i, n in enumerate(height):
if not s:
# until we find 1st bar starting to decrease height, we add it into stack
if (i < len(height)) and (i+1 < len(height)) and (height[i] > height[i+1]):
s.append((i, n))
else:
if n < s[-1][1]:
# current height less than the previous height, keep adding it
s.append((i, n))
elif n == s[-1][1]:
# current height equal to the previous height, only keep the current one
s.pop()
s.append((i, n))
else:
# current height larger than the previous height, start to compute local sub-volumes
# until all previous uncomputed sub-volumes are computed
s.append((i, n))
tmp_vol, s = self.utilLocalWaterVolume(s)
while tmp_vol > 0:
water_vol += tmp_vol
tmp_vol, s = self.utilLocalWaterVolume(s)

# if stack is not empty after traversing all elems,
# computed leftover uncomputed sub-volumes
tmp_vol, s = self.utilLocalWaterVolume(s)
while tmp_vol > 0:
water_vol += tmp_vol
tmp_vol, s = self.utilLocalWaterVolume(s)

return water_vol

def utilLocalWaterVolume(self, s):
# stack has less than 3 elevations, return 0
if len(s) < 3:
return 0, s

# each time we pick 3 consecutive heights to compute local sub-volumes
x = s[-3:]
depth = min(x[0][1], x[2][1]) - x[1][1]
width = x[2][0] - x[0][0] - 1
vol = depth*width

# heights are not in the right pattern to hold water, return 0
if depth <= 0:
return 0, s

# after computing sub-volume, we "fill" the gap with water by updating
# their heights and remove duplicate heights
if x[0][1] != x[2][1]:
del s[-3:]
tmp = [(x[0][0], x[0][1]),(x[2][0], x[2][1])]
s = s + tmp
else:
del s[-3:]
s.append((x[2][0], x[2][1]))

return vol, s
``````

This solution scans the height array one time, only using a stack to store the currently unsolved sub-volumes. It is inspired by the problem of find rectangle with maximal area under a histogram.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.