题解 | #接雨水问题#

package main

func maxWater(arr []int) int64 {
	return maxWater1(arr, 0, len(arr)-1)
	// write code here
}

func maxWater1(arr []int, st int, en int) int64 {
	if st >= en {
		return 0
	}
	sta := make([]int, len(arr))
	top := 0
	sum := make([]int64, len(arr))
	res := int64(0)
	for i := st; i <= en; i++ {
		val := arr[i]
		sum[i] = int64(val)
		if i > 0 {
			sum[i] += sum[i-1]
		}
		if top <= 0 || arr[sta[top-1]] < val {
			sta[top] = i
			top++
			if top >= 2 {
				data := (int64)(i - sta[top-2] - 1)
				data = data * (int64(arr[sta[top-2]]))
				data -= sum[i-1] - sum[sta[top-2]]
				res += data
			}
		}
	}
	maL := sta[top-1]
	top = 0
	for i := en; i >= st; i-- {
		val := arr[i]
		sum[i] = int64(val)
		if i < len(arr)-1 {
			sum[i] += sum[i+1]
		}
		if top <= 0 || arr[sta[top-1]] < val {
			sta[top] = i
			top++
			if top >= 2 {
				data := int64(sta[top-2] - i - 1)
				data = data * (int64(arr[sta[top-2]]))
				data -= sum[i+1] - sum[sta[top-2]]
				res += data
			}
		}
	}
	if maL == sta[top-1] {
		return res
	}
	data := int64(sta[top-1] - maL - 1)
	data = data * (int64(arr[sta[top-1]]))
	data -= sum[maL+1] - sum[sta[top-1]]
	res += data
	return res
}