The idea is actually similar to the O(1) space solution, but not as intuitive.

```
class Solution(object):
def trap(self, height):
if len(height) <= 2:
return 0
i = 0
lo = 0
total = 0
stk = []
while i < len(height):
if height[i] != 0:
lo = height[i]
stk = [lo]
j = i + 1
while j < len(height) and height[j] < height[i]:
stk.append(height[j])
j += 1
if j < len(height):
while stk:
total += (lo - stk.pop())
i = j - 1
i += 1
if stk:
total += self.trap(stk[::-1])
return total
```