ALG-H004HardTwo Pointers
Water Between Barriers
Each nonnegative array value is the height of a unit-width wall. Return how many unit squares of water are trapped above the bars after rainfall.
Contract
input heights: integer[]
return integer
Constraints
- • Every height >= 0
Examples
Example 1
heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
→ 6
Example 2
heights = [4, 2, 0, 3, 2, 5]
→ 9
5 judge tests (2 shown above). Target complexity: O(n).