leetcode-go/leetcode/hard/42.go

package main

func trap(height []int) (units int) {
	n := len(height)
	if n <= 2 {
		return 0
	}
	left, right := 0, n-1 // Bidirection scan is the key!!!
	maxLeft, maxRight := height[left], height[right]
	for left <= right {
		if height[left] <= height[right] { // So left bar would meet right bar
			if height[left] > maxLeft {
				maxLeft = height[left]
			} else {
				units += maxLeft - height[left]
			}
			left++
		} else { // Else, right bar would meet left bar
			if height[right] > maxRight {
				maxRight = height[right]
			} else {
				units += maxRight - height[right]
			}
			right--
		}
	}
	return
}

// func main() {
// 	h := []int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}
// 	println(trap(h))
// 	h = []int{}
// 	println(trap(h))
// }