给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10示例 2：
输入： heights = [2,4]
输出： 4提示：
- 1 <= heights.length <=105
- 0 <= heights[i] <= 104
解题：
func largestRectangleArea(heights []int) int {
length := len(heights)
if length == 0 {
return 0
}
m, temp := 0, 0
for i, v := range heights {
if v == 0 {
continue
}
l, r := i, i
for l >= 0 && heights[l] >= v {
l--
}
for r < length && heights[r] >= v {
r++
}
temp = (r - l - 1) * v
if temp > m {
m = temp
}
}
return m
}超时了。。。
官方解答：
1.单调栈
func largestRectangleArea(heights []int) int {
n := len(heights)
left, right := make([]int, n), make([]int, n)
var monoStack []int
for i := 0; i < n; i++ {
for len(monoStack) > 0 && heights[monoStack[len(monoStack)-1]] >= heights[i] {
monoStack = monoStack[:len(monoStack)-1]
}
if len(monoStack) == 0 {
left[i] = -1
} else {
left[i] = monoStack[len(monoStack)-1]
}
monoStack = append(monoStack, i)
}
monoStack = []int{}
for i := n - 1; i >= 0; i-- {
for len(monoStack) > 0 && heights[monoStack[len(monoStack)-1]] > heights[i] {
monoStack = monoStack[:len(monoStack)-1]
}
if len(monoStack) == 0 {
right[i] = n
} else {
right[i] = monoStack[len(monoStack)-1]
}
monoStack = append(monoStack, i)
}
ans := 0
for i := 0; i < n; i++ {
ans = max(ans, (right[i]-left[i]-1)*heights[i])
}
return ans
}
func max(x, y int) int {
if x > y {
return x
}
return y
}2.单调栈+常数优化
func largestRectangleArea(heights []int) int {
n := len(heights)
left, right := make([]int, n), make([]int, n)
for i := 0; i < n; i++ {
right[i] = n
}
var monoStack []int
for i := 0; i < n; i++ {
for len(monoStack) > 0 && heights[monoStack[len(monoStack)-1]] >= heights[i] {
right[monoStack[len(monoStack)-1]] = i
monoStack = monoStack[:len(monoStack)-1]
}
if len(monoStack) == 0 {
left[i] = -1
} else {
left[i] = monoStack[len(monoStack)-1]
}
monoStack = append(monoStack, i)
}
ans := 0
for i := 0; i < n; i++ {
ans = max(ans, (right[i]-left[i]-1)*heights[i])
}
return ans
}
func max(x, y int) int {
if x > y {
return x
}
return y
}