Given an array of non-negative integers representing the height of each bar in a histogram with a width of 1, calculate how much rainwater can be trapped after it rains.
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above is a height map represented by the array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, it is possible to trap 6 units of rainwater (the blue area represents the rainwater).
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
Note:
- n == height.length
- 1 <= n <= 2 * 104
- 0 <= height[i] <= 105
Solution 1: Monotonic Stack
Algorithm:
For each bar in the histogram, if it is lower than the top bar in the stack, push it onto the stack. If it is higher, calculate the amount of trapped rainwater and update the stack accordingly. The trapped rainwater can be calculated by finding the minimum height between the current bar and the top bar in the stack, and multiplying it by the width (the difference in indices). Add this amount to the total trapped rainwater. Repeat this process until all bars have been processed.
func trap(height []int) int {
stack := make([]int, 0)
ret := 0
for i := 0; i < len(height); i++ {
for len(stack) != 0 && height[stack[len(stack)-1]] < height[i] {
cur := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if len(stack) == 0 {
break
}
h := height[i]
if height[stack[len(stack)-1]] < h {
h = height[stack[len(stack)-1]]
}
w := i - stack[len(stack)-1] - 1
ret += w * (h - height[cur])
}
stack = append(stack, i)
}
return ret
}
Solution 2: Check if the current bar can hold water based on the maximum heights on the left and right sides
func max_num(arr []int) int {
max := 0
for i:= 0; i< len(arr);i++ {
x := arr[i]
if x > max {
max = x
}
}
return max
}
func trap(height []int) int {
left_max_arr := make([]int, 0)
right_max_arr := make([]int, 0)
ret := 0
for i:=0;i<len(height);i++ {
left_max_arr = append(left_max_arr, max_num(height[:i]))
right_max_arr = append(right_max_arr, max_num(height[i:]))
}
for i:=0;i<len(height);i++ {
if left_max_arr[i] < right_max_arr[i] {
if left_max_arr[i]> height[i] {
ret += left_max_arr[i] - height[i]
}
}else{
if right_max_arr[i] > height[i] {
ret += right_max_arr[i] - height[i]
}
}
}
return ret
}
Solution 3: Two Pointer Approach
From the previous solution, it is easy to derive the two pointer approach, which reduces the space complexity from O(n) to O(1).
func trap(height []int) int {
left := 0
right := len(height)-1
left_max := 0
right_max := 0
ret := 0
for left < right {
water_level := left_max
if left_max > right_max {
water_level = right_max
}
if height[left] <= water_level {
ret += water_level-height[left]
left += 1
continue
}
if height[right] <= water_level {
ret += water_level-height[right]
right -= 1
continue
}
if left_max < height[left] {
left_max = height[left]
}
if right_max < height[right] {
right_max = height[right]
}
}
return ret
}