题目地址(84. 柱状图中最大的矩形)
https://leetcode.cn/problems/largest-rectangle-in-histogram/
题目描述
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
前置知识
公司
- 暂无
思路
- 朴素的思路：枚举每一根柱子，然后向两边扩展，使得扩展到的柱子的高度均不小于h。也就是找到左右两个边界，也即左右两侧最近的高度小于h的柱子，这样两根柱子之间的所有柱子高度均不小于h。
- 那么怎么找左右边界？使用单调栈即可
1）栈中存放了j值。从栈底到栈顶，j的值严格单调递增，同时对应的高度值也严格单调递增；
2）当我们枚举到第 i 根柱子时，我们从栈顶不断地移除height[j] ≥ height[i] 的 j 值。在移除完毕后，栈顶的 j 值就一定满足height[j] < height[i]，此时 j 就是 i 左侧且最近的小于其高度的柱子。
3）我们再将 i 放入栈顶。 - 优化：只遍历一次就能确定答案
对位置i进行入栈时，确定了它的左边界。
对位置i进行出栈时，可以确定它的有边界。当i被弹出栈是，说明此时遍历到的位置j的高度小于等于height[i]，并且在i与j之间没有其他高度小于等于height[i]的柱子。如果有的话，则在遍历那个位置的时候，i应该已经被弹出栈了。所以，j就是位置i的右边界。、 - 因此，一个非常重要的结论显而易见：i的左边界就是栈中的下一位，i的右边界，就是当i被弹出时遍历到的位置。
关键点
代码
- 语言支持：Go
Go Code:
func largestRectangleArea(heights []int) int {
if len(heights) == 0 {
return 0
}
if len(heights) == 1 {
return heights[0]
}
stack := []int{-1}
n := len(heights)
res := 0
for i := 0; i < n; i++ {
for len(stack) > 1 && (heights[i] < heights[stack[len(stack) - 1]]) {
area := (i - stack[len(stack) - 2] - 1) * heights[stack[len(stack) - 1]]
stack = stack[:len(stack) - 1]
if area > res {
res = area
}
}
stack = append(stack, i)
}
for len(stack) > 1 {
area := (n - stack[len(stack) - 2] - 1) * heights[stack[len(stack) - 1]]
stack = stack[:len(stack) - 1]
if area > res {
res = area
}
}
return res
}
更简单的写法，在原数组中加一个0，就可以去掉最后边界情况的循环，因为0比任何正数都小：
func largestRectangleArea(heights []int) int {
if len(heights) == 0 {
return 0
}
if len(heights) == 1 {
return heights[0]
}
stack := []int{-1}
heights = append(heights, 0)
n := len(heights)
res := 0
for i := 0; i < n; i++ {
for len(stack) > 1 && (heights[i] < heights[stack[len(stack) - 1]]) {
area := (i - stack[len(stack) - 2] - 1) * heights[stack[len(stack) - 1]]
stack = stack[:len(stack) - 1]
if area > res {
res = area
}
}
stack = append(stack, i)
}
return res
}
复杂度分析
令 n 为数组长度。
- 时间复杂度：
- 空间复杂度：
