柱状图中接雨水、找方块

func trap(height []int) int {
	n := len(height)
	if n == 0 {
		return 0
	}

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

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

	res := 0
	for i, h := range height {
		res += min(prefixMax[i], suffixMax[i]) - h
	}
	return res
}

func trap(height []int) int {
	n := len(height)
	if n < 3 {
		return 0
	}
	left, right := 0, n-1
	leftPeek, rightPeek := 0, 0
	res := 0
	for left < right {
		leftVal, rightVal := height[left], height[right]
		leftPeek = max(leftPeek, leftVal)
		rightPeek = max(rightPeek, rightVal)
		if leftVal < rightVal { // 处理左侧
			res += leftPeek - leftVal
			left++
		} else { // 处理右侧
			res += rightPeek - rightVal
			right--
		}
	}
	return res
}

func trap1(height []int) int {
	n := len(height)
	if n < 3 {
		return 0
	}
	res := 0
	var stack []int // 记录可能存水的柱子索引
	for i, v := range height {
		for len(stack) > 0 && v > height[stack[len(stack)-1]] {
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			if len(stack) == 0 {
				break
			}
			newTop := stack[len(stack)-1]
			width := i - newTop - 1
			boundHeight := min(v, height[newTop]) - height[top]
			res += width * boundHeight
		}
		stack = append(stack, i)
	}
	return res
}

func largestRectangleArea(heights []int) int {
	res := 0
	for i := range heights {
		for j := i; j < len(heights); j++ {
			res = max(res, (j - i + 1) * min(heights[i:j+1]))
		}
	}
	return res
}

func largestRectangleArea02(heights []int) int {
   res := 0
   for i, h := range heights {
      width := 0
      for left := i; left >= 1 && heights[left-1] >= h; left-- {
         width++
      }
      for right := i; right < len(heights)-1 && heights[right+1] >= h; right++ {
         width++
      }
      res = max(res, width*h)
   }
   return res
}

func largestRectangleArea(heights []int) int {
	left, right := calLeft(heights), calRight(heights)
	res := 0
	for i, h := range heights {
		res = max(res, (right[i]-left[i]-1)*h)
	}
	return res
}

// 找到每个位置左侧距离最近且高度小于当前位置高度的位置
func calLeft(heights []int) []int {
	res := make([]int, len(heights))
	stack := list.New()
	for i, h := range heights {
		for stack.Len() > 0 && heights[stack.Back().Value.(int)] >= h {
			stack.Remove(stack.Back())
		}
		if stack.Len() == 0 {
			res[i] = -1
		} else {
			res[i] = stack.Back().Value.(int)
		}
		stack.PushBack(i)
	}
	return res
}

// 找到每个位置右侧距离最近且高度小于当前位置的位置
func calRight(heights []int) []int {
	res := make([]int, len(heights))
	stack := list.New()
	for i := len(heights) - 1; i >= 0; i-- {
		for stack.Len() > 0 && heights[stack.Back().Value.(int)] >= heights[i] {
			stack.Remove(stack.Back())
		}
		if stack.Len() == 0 {
			res[i] = len(heights)
		} else {
			res[i] = stack.Back().Value.(int)
		}
		stack.PushBack(i)
	}
	return res
}