代码随想录训练营 单调栈

最后一天~

84. 柱状图中最大的矩形🌸

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

func largestRectangleArea(heights []int) int {// 声明max并初始化为0max := 0// 使用切片实现栈stack := make([]int, 0)// 数组头部加入0heights = append([]int{0}, heights...)// 数组尾部加入0heights = append(heights, 0)// 初始化栈，序号从0开始stack = append(stack, 0)for i := 1; i < len(heights); i++ {// 结束循环条件为：当即将入栈元素>top元素，也就是形成非单调递增的趋势for heights[stack[len(stack)-1]] > heights[i] {// mid 是topmid := stack[len(stack)-1]// 出栈stack = stack[0 : len(stack)-1]// left是top的下一位元素，i是将要入栈的元素left := stack[len(stack)-1]// 高度x宽度tmp := heights[mid] * (i - left - 1)if tmp > max {max = tmp}}stack = append(stack, i)}return max
}