分析：
核心思想：欲求面积最大的矩形，可以确定该矩形的高度一定是 heights 数组中的元素。然后就可以枚举每个柱子的高度，找到每个柱子左右首个低于它的柱子的位置。
假设 h = heights[i] 是矩形的高度，其左右边界，即宽度最大是多少？
- 在 i 左侧的小于 heights[i] 的最近元素的下标 left，如果不存在则为 -1。此时 left + 1 就是矩形最左边的那根柱子。
- 在 i 右侧的小于 heights[i] 的最近元素的下标 right，如果不存在则为 n。此时 right – 1 就是矩形最右边的那根柱子。
因此矩形宽度为 right – 1 – (left + 1) + 1 = right – left – 1。因此最终的矩形面积为 h * (right – left – 1)。
题目给出的示例，可以得出选择 i = 2 这个柱子作为矩形的高，左边小于 heights[2] = 5 的最近元素的下标 left = 1，右边小于 heights[2] = 5 的最近元素的下标 right = 4，所以矩形的宽度是 right – left – 1 = 2，矩形面积为 h * (right – left – 1) = 5 * 2 = 10。
然后枚举出所有 i 对应矩形面积，取其最大为最终结果。
实现代码如下:
func largestRectangleArea(heights []int) int {
n := len(heights)
// 确定每个h对应的最左边的那根柱子, left + 1
left := make([]int, n)
st := []int{-1}
for i, h := range heights {
for len(st) > 1 && h <= heights[st[len(st) - 1]] {
st = st[:len(st) - 1]
}
left[i] = st[len(st) - 1]
st = append(st, i)
}
// 确定每个h对应的最右边的那根柱子,right - 1
right := make([]int, n)
st = st[:1]
st[0] = n
for i, h := range slices.Backward(heights) {
for len(st) > 1 && h <= heights[st[len(st) - 1]] {// 这里heights[len(st) - 1]表示的是当前遍历的h的右边的数字
st = st[:len(st) - 1]
}
right[i] = st[len(st) - 1]
st = append(st, i)
}
// 遍历整个heights求出最大面积
// 宽度为 right - 1 - (left + 1) + 1 = right - left - 1
var result int
for i, h := range heights {
result = max(result, h * (right[i]- left[i] - 1))
}
return result
}解析：
在求左边柱子时定义的 st := []{-1}，本身目的是作为一个栈，初始化为 [-1] 。在循环中，对于每个索引 i 和高度 h，用来检查栈中是否不止有 -1 （len(st) > 1）且当前高度 h 小于等于栈顶索引对应的高度。如果是，则弹出栈顶。然后，将当前 left[i] 设置为栈顶索引(st[len(st) – 1])，并将当前索引 i 压入栈。弹栈的操作要一直进行直到不满足条件才可以停止。
left := make([]int, n)
st := []int{-1}
for i, h := range heights {
for len(st) > 1 && h <= heights[st[len(st) - 1]] {
st = st[:len(st) - 1]
}
left[i] = st[len(st) - 1]
st = append(st, i)
}这就是上述代码的核心思想。
同理，求右边柱子时定义的 st := [] {n}。但是需要注意的是，再求左边柱子的时候，h 比较的是左侧柱子，因此是按 heights 的索引升序遍历。那么再求右边柱子的时候，h 比较的是右侧柱子，需要按 heights 的索引降序遍历。这里用到了 go 语言的基础库 slices 包下的 backward 方法，可以直接反向遍历数组，非常的方便。
参考链接：https://pkg.go.dev/slices#Backward
最后，遍历整个 heights 数组，结合前面求得的 left 和 right 数组，计算最大矩形面积即可。
复杂度分析：
使用三次遍历的方式来求解改题目
- 时间复杂度：O(n)，其中 n 是 heights 的长度。每个元素入栈和出栈都至多是一次，所以是 O(n) 的。
- 空间复杂度：O(n)。
No responses yet