0084.柱状图中最大的矩形

https://leetcode.cn/problems/largest-rectangle-in-histogram/

方法一：单调栈

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

func largestRectangleArea(heights []int) int {
	left, right, stack, n := make([]int, len(heights)), make([]int, len(heights)), []int{}, len(heights)
	for i := 0; i < n; i++ {
		for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
			stack = stack[:len(stack)-1]
		}
		left[i] = -1
		if len(stack) > 0 {
			left[i] = stack[len(stack)-1]
		}
		stack = append(stack, i)
	}
	stack = []int{}
	for i := n - 1; i >= 0; i-- {
		for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
			stack = stack[:len(stack)-1]
		}
		right[i] = n
		if len(stack) > 0 {
			right[i] = stack[len(stack)-1]
		}
		stack = append(stack, i)
	}
	ans := 0
	for i := 0; i < n; i++ {
		area := (right[i] - left[i] - 1) * heights[i]
		if area > ans {
			ans = area
		}
	}
	return ans
}

方法二：单调栈 + 常数优化

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

func largestRectangleArea(heights []int) int {
	left, right, stack, n := make([]int, len(heights)), make([]int, len(heights)), []int{}, len(heights)
	for i := 0; i < n; i++ {
		for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
			right[stack[len(stack)-1]] = i
			stack = stack[:len(stack)-1]
		}
		left[i] = -1
		if len(stack) > 0 {
			left[i] = stack[len(stack)-1]
		}
		stack = append(stack, i)
	}
	for i := 0; i < len(stack); i++ {
		right[stack[i]] = n
	}
	ans := 0
	for i := 0; i < n; i++ {
		area := (right[i] - left[i] - 1) * heights[i]
		if area > ans {
			ans = area
		}
	}
	return ans
}