Write a function trap
that calculates how much rainwater can be trapped between bars in a histogram after raining.
Given an array of non-negative integers height
where each element represents the elevation at that point, compute how much water it can trap.
function trap(height: number[]): number;
trap([0,1,0,2,1,0,1,3,2,1,2,1]); // 6 trap([4,2,0,3,2,5]); // 9
Each bar's trapped water is determined by the minimum of the highest bars to its left and right, minus its own height.
For example, in [0,1,0,2,1,0,1,3,2,1,2,1]
, at index 5 (height = 0
):
min(2, 3) - 0 = 2
.The total water trapped is the sum across all indices.
n == height.length
0 ≤ n ≤ 10⁵
0 ≤ height[i] ≤ 10⁴
O(n)
time and O(1)
extra space.function trap(height: number[]): number;
trap([0,1,0,2,1,0,1,3,2,1,2,1]); // 6
trap([4,2,0,3,2,5]); // 9