84. Largest Rectangle in Histogram
原题
84. Largest Rectangle in Histogram
解答思路
本题的核心思路是采用递增栈来做，但为什么？
这是因为，在计算柱状图中的矩形面积时，核心思想是关注每个Bar所在最大矩阵的面积是多少。因为当前这个Bar_x的高度是已知的，那我们想知道的就是这个Bar_x所在矩形的最大的宽是多少。那显然向左向右的Bar里面，比当前Bar_x的高度更高的部分是可以加入这个矩形的，因此我们只需要知道Bar_x向左向右第一个小于其高度的Bar。因此，我们用递增栈就可以解决这一问题！
令Bar_x是栈顶元素，那么左边界就是栈顶的下一个元素(假设下标为j)，而右边界就是触发弹栈时的元素(假设下标为i)。那么这部分矩形的面积就是height[Bar_x] * (i-j-1)。
那如果左边界不存在呢？即，弹出Bar_x后栈空了。既然我们构建的栈是递增栈，此时说明Bar_x左侧没有比他更小的栈了，所以左边界本身就在0的位置！因此，此时宽度直接可以设置为i。
此外，需要注意的是，为了清空栈内的剩余的柱保证面积都能得到统计，需要用到一个额外的高度为0的虚拟柱。
代码
func largestRectangleArea(heights []int) int {
n := len(heights)
if n == 0 {
return 0
}
ans := 0
stk := []int{}
for i := 0; i <= n; i++ {
var h int
if i == n {
h = 0
} else {
h = heights[i]
}
// 构建递增栈
for len(stk) > 0 && h < heights[stk[len(stk)-1]] {
// 弹栈
top := stk[len(stk)-1]
stk = stk[:len(stk)-1]
// 计算宽度
width := i // 栈空时，说明top的左边界为0, 宽度为i
if len(stk) > 0 {
// 说明左侧还有比Bar_x更小的
left := stk[len(stk)-1] //左边界的值
width = i - left - 1
}
area := heights[top] * width
ans = max(ans, area)
}
// 入栈
stk = append(stk, i)
}
return ans
}
