essay
hot100-柱状图中最大的矩形
#算法
hot100——柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4]
输出： 4
提示：
1 <= heights.length <=
0 <= heights[i] <=
解法
func largestRectangleArea(heights []int) int {
res := 0
heights = append(heights, 0) // 在末尾添加高度为0的柱子，确保所有柱子都能被处理
stack := []int{-1} // 栈中存放柱子的索引，初始放入 -1 作为左边界哨兵
for i := 0; i < len(heights); i++ {
for len(stack) > 1 && heights[i] < heights[stack[len(stack)-1]] {
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
// 长度 = heights[top]
// 宽度 = 右边界 - 左边界 - 1
res = max(res, heights[top] * (i-stack[len(stack)-1]-1))
}
stack = append(stack, i)
}
return res
}