Rain between the walls
Work out how much rain a row of walls can hold, filling layer by layer whenever a taller wall closes a dip. About 20 minutes.
A dip is closed by a taller wall
Water sits in a dip: a low bar with a taller wall on each side. Keep a stack of walls whose heights go down from the bottom of the stack to the top. A wall that is not taller than the top is simply pushed, because nothing has closed a dip yet.
When a wall arrives that is taller than the top, the top is the bottom of a dip, closed on the right by this new wall.
dip, left_wall, right_wall = 0, 3, 2 level = min(left_wall, right_wall) - dip
4 and 1 are pushed, since 1 is not taller than 4. Stack heights: 4, 1.
Fill one layer
After popping the bottom, the new top of the stack is the wall on its left. If there is none, the dip has no left side and holds nothing, so stop.
Otherwise the water here is a layer. Its width is the space between the left wall and the new wall. Its height is the lower of the two walls, minus the height of the bottom, because the water below the bottom has been counted already.
water = 0 water += 2 * 3 # 2 wide, 3 deep
A taller wall pops a bottom and the stack is then empty. How much water is added?
- ANone, since the dip has no wall on its left
- BThe distance from the start of the row
- CThe bottom's height
Show the answer
None, since the dip has no wall on its left. Water needs a wall on both sides.
Trapping rain water
You are given an array height of non-negative integers, the heights of bars of width 1 standing side by side. After it rains, water collects between the bars. Return the total units of water held. Water at a position is held up to the lower of the tallest bar on its left and the tallest on its right.
height = [3, 0, 2, 0, 4] → 7
0 ≤ length of height ≤ 100,000 · 0 ≤ height[i] ≤ 100,000