Trapping Rain Water

A row of bars, each one unit wide, stands on flat ground, and heights[i] is the height of bar i. Rain falls on all of it. Water runs off both ends of the row, but wherever taller bars on both sides hold it in, it stays. Write trapped_water(heights) that returns how many units of water stay trapped.

Examples

trapped_water([3, 0, 2, 0, 4])               # returns 7
trapped_water([0, 2, 0, 1, 0, 3, 1, 0, 2])   # returns 8
trapped_water([1, 2, 3, 4])                  # returns 0

In the first example the outer bars of height 3 and 4 hold water up to level 3: that is 3 units above the first gap, 1 above the bar of height 2 and 3 above the second gap, 7 in total. In the last example every drop runs off to the left.

Constraints

• 0 <= len(heights) <= 100,000
• 0 <= heights[i] <= 10,000

Note

Aim for a single pass over the bars that uses a few variables and no extra lists.