Given n non-negative integers height describing an elevation map where every bar has width 1, compute how much water it can trap after it rains.
Examples
Example 1
- Input
- height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
- Output
- 6
Example 2
- Input
- height = [4, 2, 0, 3, 2, 5]
- Output
- 9
Constraints
1 <= height.length <= 2 * 10^40 <= height[i] <= 10^5