height describes a row of bars, each one unit wide, standing side by side. After it rains, water settles in the dips between taller bars. Return how many units of water stay trapped.
Water above a bar can rise only to the lower of the tallest bar on its left and the tallest bar on its right; anything higher spills over.
Between the walls of height 3 and 4, the water reaches 3: that holds 3 + 2 + 3 = 8 units. Between 4 and 2 it reaches 2, one more column: 2. In all, 10.
Constraints
n == height.length1 <= n <= 2 × 10⁴0 <= height[i] <= 10⁵The water above bar i is min(tallest bar to its left, tallest bar to its right) − height[i], when that is positive.
Look at one bar at a time and ask how high the water stands above it. Water over bar i is held in by a wall on each side. On the left, the best wall is the tallest bar anywhere to its left; on the right, the tallest bar anywhere to its right. The water can rise only as high as the lower of those two walls, because above that it spills out over the lower side.
Time O(n)Space O(1)
The full walkthrough and code are part of Premium
10