Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water can be trapped after raining.
The input is an array height, where height[i] is the height of the ith bar. Return the total number of units of rain water trapped between the bars.
Example 1
#
# # # #
# # # # # # # # #
0 1 0 2 1 0 1 3 2 1 2 1Input
height = [0,1,0,2,1,0,1,3,2,1,2,1]Output
6The elevation map traps 6 total units of water across the valleys between taller bars.
Example 2
# # # # # # # # # # # # # # # # 4 2 0 3 2 5
Input
height = [4,2,0,3,2,5]Output
9Water is trapped above the bars of heights 2, 0, 3, and 2 for a total of 9 units.
Constraints
- 1 <= height.length <= 2 * 10^4
- 0 <= height[i] <= 10^5