Rainwater Trapping
Medium
Given an array of integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example 1
Input
[ 0, 1, 0, 2, 1, 0, 3, 1, 0, 1, 2 ]
Output
8
Explanation. After the rain, water is trapped between the elevations. The area of water trapped is 8.
Example 2
Input
[ 4, 2, 0, 3, 2, 5 ]
Output
9
Explanation. Water can be trapped on top of the bars between the indices 1 through 4 and 3 through 5.
Example 3
Input
[ 3, 0, 2 ]
Output
2
Explanation. Water is trapped between the bars at index 0 and 2, directly above index 1.
Example 4
Input
[ 0, 2, 0 ]
Output
0
Explanation. No elevation surrounds a low point to contain water.
Follow-up: Can you implement an solution that runs in O(n) time and uses O(1) extra space?
Constraints:
The number of elements in the array is greater than 0 and less than 10,000. All elements in the array will be non-negative integers less than or equal to 100,000.
- Views
- 13