力扣 84. 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
方案一：构建单调递增栈。因为每遇到右边的高度低于左边， 就表示当前的柱子的高度无法再应用到右边柱子，此时应该计算一次最大矩形面积。
// rect 矩形。
type rect struct {
width int
height int
}
func largestRectangleArea(heights []int) int {
ans := 0
// 构建单调递增栈，高的柱子遇到矮的柱子可以贡献自身高度
stk := make([]*rect, 0, len(heights))
// 在柱形图末尾补零，保证触发单调递增栈的出栈逻辑
heights = append(heights, 0)
for _, h := range heights {
acculmatedWidth := 0
// 如果栈不空，并且无法构成递增（此时需要出栈栈顶）
for len(stk) > 0 && stk[len(stk) - 1].height > h {
// 取栈顶
top := stk[len(stk) - 1]
// 累积宽度(高的柱子贡献了自己的宽度)
acculmatedWidth += top.width
// 计算最大值
ans = max(ans, acculmatedWidth * top.height)
// 出栈
stk = stk[:len(stk) - 1]
}
// +1 加的是自身的宽度
acculmatedWidth += 1
// 入栈当前矩形
// acculmatedWidth 中包含了如果无法构成单调增而出栈的柱子的宽度
stk = append(stk, &rect{
width: acculmatedWidth,
height: h,
})
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func largestRectangleArea(heights []int) (ans int) {
// 定义单调递增栈，数组元素为 heights 下标
stk := make([]int, 0, len(heights))
// 在数组末尾补上一个题目给定范围的最小值，保证破坏栈内元素单调性
heights = append(heights, 0)
for i, height := range heights {
for len(stk) > 0 {
// 取栈顶
top := stk[len(stk) -1]
// 满足单调性，停止本次内循环
if heights[top] <= height {
break
}
// 元素出栈
stk = stk[:len(stk) - 1]
// 如果此时栈中没有元素，表示 0～index-1 之间的宽度的最高公共长度为 heights[top]
// 否则就是栈中上一个元素的下标和当前元素下标的差 - 1（宽度） * heights[top]
if len(stk) > 0 {
ans = max(ans, (i - stk[len(stk) - 1] - 1) * heights[top])
} else {
ans = max(ans, heights[top] * i)
}
}
stk = append(stk, i)
}
return
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
- 时间复杂度：O(n)，因为需要遍历数组中所有元素，虽然遍历途中有入栈出栈的遍历操作（每个元素最多出入一次），但是均摊后时间复杂度还是在 O(n)。
- 空间复杂度：O(n)，因为使用了数个长度不超过 n 的单调栈，所以空间复杂度为 O(n)。