/*
 * @lc app=leetcode.cn id=42 lang=golang
 *
 * [42] 接雨水
 */

// @lc code=start
func trap(heights []int) int {
	left, right, res1 := 0, 1, 0
	for right < len(heights) {
		if heights[left] >= heights[right] {
			res1 += heights[left] - heights[right]
			right++
		} else {
			left = right
			right++
		}
	}
	left, right = len(heights)-2, len(heights)-1
	res2 := 0
	for left >= 0 {
		if heights[right] >= heights[left] {
			res2 += heights[right] - heights[left]
			left--
		} else {
			right = left
			left--
		}
	}

	// 虽然绕点，但结局还是好的
	whiteAndWater := len(heights)*maxArr(heights) - sum(heights)
	whiteAnd2Water := res1 + res2
	return whiteAnd2Water - whiteAndWater
}

func sum(arr []int) int {
	val := 0
	for i := 0; i < len(arr); i++ {
		val += arr[i]
	}
	return val
}

func maxArr(arr []int) int {
	maxVal := 0
	for i := 0; i < len(arr); i++ {
		maxVal = max(maxVal, arr[i])
	}
	return maxVal
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

// @lc code=end

// 官方的双指针
func trap(height []int) (ans int) {
	left, right := 0, len(height)-1
	leftMax, rightMax := 0, 0
	for left < right {
		leftMax = max(leftMax, height[left])
		rightMax = max(rightMax, height[right])
		if height[left] < height[right] {
			ans += leftMax - height[left]
			left++
		} else {
			ans += rightMax - height[right]
			right--
		}
	}
	return
}

// 官方的单调栈
func trap(height []int) (ans int) {
	stack := []int{}
	for i, h := range height {
		for len(stack) > 0 && h > height[stack[len(stack)-1]] {
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			if len(stack) == 0 {
				break
			}
			left := stack[len(stack)-1]
			curWidth := i - left - 1
			curHeight := min(height[left], h) - height[top]
			ans += curWidth * curHeight
		}
		stack = append(stack, i)
	}
	return
}

// 官方的动态规划
func trap(height []int) (ans int) {
	n := len(height)
	if n == 0 {
		return
	}

	leftMax := make([]int, n)
	leftMax[0] = height[0]
	for i := 1; i < n; i++ {
		leftMax[i] = max(leftMax[i-1], height[i])
	}

	rightMax := make([]int, n)
	rightMax[n-1] = height[n-1]
	for i := n - 2; i >= 0; i-- {
		rightMax[i] = max(rightMax[i+1], height[i])
	}

	for i, h := range height {
		ans += min(leftMax[i], rightMax[i]) - h
	}
	return
}