Trapping Rain Water
heights describes a row of bars of width 1, heights[i] tall. After it rains, water collects in the dips between bars. Return how many units of water the row holds.
Constraints
- 1 ≤ length of
heights≤ 100,000 - 0 ≤
heights[i]≤ 10,000
Example 1
Input
heights = [0,1,0,2,1,0,1,3,2,1,2,1]
Output
6
Why:
1 unit at position 2, 4 between positions 3 and 7, and 1 at position 9.
Example 2
Input
heights = [4,2,0,3,2,5]
Output
9
Why:
Everything between the 4 and the 5 fills to height 4: 2 + 4 + 1 + 2.
Hints
Was this a good challenge?
- Solved by
- 0
- Submissions
- 0
- Accepted
- –