func largestRectangleArea(heights []int) int {
maxArea := 0
var height = make([]int, 0)
height = append(height, []int{0}...)
height = append(height, heights...)
height = append(height, []int{0}...)
stack := make([]int, 0)
for index:=0; index < len(height); index++{
// 当前元素height[index]小于栈顶元素时，开始计算栈顶元素height[stack[len(stack)-1]]的面积
for len(stack) > 0 && height[index] < height[stack[len(stack)-1]]{
// 栈顶元素
top := stack[len(stack)-1]
// 出栈
stack = stack[:len(stack)-1]
left := stack[len(stack)-1]
right := index
area := (right - left - 1) * height[top]
maxArea = max(maxArea, area)
}
// 进栈
stack= append(stack,index)
}
return maxArea
}
- 单调递增栈：
①在一个队列中针对每一个元素从它右边寻找第一个比它小的元素
②在一个队列中针对每一个元素从它左边寻找第一个比它小的元素（从后往前遍历）
