OneNoughtOne
0/364
Loading content...
You are given an array of non-negative integers representing the elevation profile of a terrain, where each element corresponds to the height of a vertical bar at that position. All bars have a uniform width of 1 unit. After a rainstorm, water accumulates in the depressions formed between the elevated bars.
Your task is to determine the total volume of water that can be retained in the terrain after rainfall. Water can only be held in areas where it is bounded by higher elevations on both sides, effectively creating basins or valleys that collect and retain water.
Consider that:
elevations = [0,1,0,2,1,0,1,3,2,1,2,1]6Explanation
The terrain profile creates several basins. Between index 1 (height 1) and index 3 (height 2), there is a depression at index 2 that holds 1 unit of water. The largest basin forms between indices 3 and 7, where the valley at positions 4, 5, and 6 accumulates water bounded by heights 2 and 3. Similarly, smaller basins exist between indices 7-10. The total accumulated water volume is 6 units.
elevations = [4,2,0,3,2,5]9Explanation
This terrain has a significant basin between the first element (height 4) and the last element (height 5). The intermediate positions at heights 2, 0, 3, and 2 can hold water up to the minimum of the boundary heights (which is 4). Position 1 holds 4-2=2 units, position 2 holds 4-0=4 units, position 3 holds 4-3=1 unit, and position 4 holds 4-2=2 units. Total: 2+4+1+2 = 9 units.
elevations = [3,0,3]3Explanation
A simple basin with equal height boundaries. The depression at index 1 (height 0) is bounded by elevations of 3 on both sides. The water level rises to height 3, filling the gap completely and retaining 3 units of water.
Constraints