Description
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Examples
Input:
height = [0,1,0,2,1,0,1,3,2,1,2,1]Output:
6Explanation:
Water trapped in valleys: index 2 holds 1, index 4 holds 1, index 5 holds 2, index 6 holds 1, index 9 holds 1 = 6 units.
Input:
height = [4,2,0,3,2,5]Output:
9Explanation:
Bounded by heights 4 and 5, indices 1-4 trap water: 2+4+1+2 = 9 units total.
Input:
height = [1,2,3,4,5]Output:
0Explanation:
Monotonically increasing terrain has no valleys to trap water.
Constraints
- •
n == height.length - •
1 ≤ n ≤ 2 × 10⁴ - •
0 ≤ height[i] ≤ 10⁵