aloalgoTrapping Rain Water
You are given an array of non-negative integers heights representing an elevation map where the width of each bar is 1.
Your task is to compute how much water it can trap after raining.
Example 1
[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
6
The elevation map [0,1,0,2,1,0,1,3,2,1,2,1] traps 6 units of rain water. For instance, at index 2 (height 0), water trapped is min(max_left=1, max_right=3) - 0 = 1. At index 5 (height 0), water trapped is min(max_left=2, max_right=3) - 0 = 2. Summing up all such trapped water yields 6.
Example 2
[4, 2, 0, 3, 2, 5]
9
The elevation map [4,2,0,3,2,5] traps 9 units of water. For example: at index 1 (height 2), water = min(4,5) - 2 = 2. At index 2 (height 0), water = min(4,5) - 0 = 4. At index 3 (height 3), water = min(4,5) - 3 = 1. At index 4 (height 2), water = min(4,5) - 2 = 2. Total water = 2+4+1+2 = 9.
Example 3
[5, 4, 3, 2, 1, 2, 3, 4, 5]
16
The elevation map [5,4,3,2,1,2,3,4,5] traps 16 units of water. The central valley allows significant water accumulation. For instance, over the bar of height 1, 4 units of water are trapped (min(5,5) - 1 = 4).
[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
6