package Stack
import (
"math"
)
func largestRectangleArea(heights []int) int {
size := len(heights)
leftLess, rightLess := make([]int, size), make([]int, size)
stack := new(Stack[int])
// (1) 遍历阶段
for i := 0; i < size; i++ {
for !stack.IsEmpty() && heights[i] <= heights[stack.Top()] {
cur := stack.Pop()
if stack.IsEmpty() {
leftLess[cur] = -1
} else {
leftLess[cur] = stack.Top()
}
rightLess[cur] = i
}
stack.Push(i)
}
// (2) 清算阶段
for !stack.IsEmpty() {
cur := stack.Pop()
if stack.IsEmpty() {
leftLess[cur] = -1
} else {
leftLess[cur] = stack.Top()
}
rightLess[cur] = size
}
// (3) 修正阶段
for i := size - 1; i >= 0; i-- {
if rightLess[i] < size && heights[i] == heights[rightLess[i]] {
rightLess[i] = rightLess[rightLess[i]]
}
}
result := math.MinInt
for i := 0; i < size; i++ {
curArea := (rightLess[i] - leftLess[i] - 1) * heights[i]
result = max(result, curArea)
}
return result
}