剑指 Offer II 039. 直方图最大矩形面积（经典题）

力扣

给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：

输入： heights = [2,4]
输出： 4
 

提示：

1 <= heights.length <=105
0 <= heights[i] <= 104

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/0ynMMM
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

单调栈一遍遍历

解法思想：单调栈-双向遍历一样，考虑从左向右一次遍历即可确定左右两个边界，直接确定某个高度的最大矩形面积，进而确定整个直方图的矩形面积。

从左到右逐一扫描数组中的每个柱子高度，如果当前柱子高度大于栈顶柱子高度，将该柱子下标入栈；否则，将栈顶的柱子下标出栈。

在出栈时直接计算出栈元素为高时的最大矩形面积，左边第一个低于该高的柱子下标是栈顶元素left（栈空为-1），右边第一个低于该高的柱子下标是当前柱子下标right。

在遍历结束，栈中还会维护着一个递增序列，依次弹出计算，左边第一个低于该高的柱子下标是栈顶元素left（栈空为-1），右边第一个低于该高的柱子下标是heights数组最大下标加1，也就是heights.length。

小优化：在原heights数组前后各增加哨兵元素0，代表直方图左右各有一个高度无穷小的柱子，只需要遍历一次，简化计算。

时间复杂度O(n) 空间复杂度O(n)

class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        stack = []
        stack.append(0)
        heights.insert(0, 0)
        heights.append(0)
        maxArea = 0
        for i in range(1,len(heights)):
            while heights[stack[-1]] > heights[i]:
                height = heights[stack.pop()]
                width = i - stack[-1] - 1
                maxArea = max(maxArea, height * width)
            stack.append(i)
        return maxArea

type stack []int

func (s *stack) push(i int) {
	*s = append(*s, i)
}

func (s *stack) pop() int {
	a := *s
	i := a[len(a)-1]
	*s = a[:len(a)-1]
	return i
}

func (s *stack) top() int {
	a := *s
	return a[len(a)-1]
}

func largestRectangleArea(heights []int) int {
	var stack stack
	addDummy := make([]int, len(heights)+2)
	for i := 0; i < len(heights); i++ {
		addDummy[i+1] = heights[i]
	}
	heights = addDummy
	stack.push(0)
	maxArea := 0
	for i := 1; i < len(heights); i++ {
		for heights[stack.top()] > heights[i] {
			height := heights[stack.pop()]
			width := i - stack.top() - 1
			if height*width > maxArea {
				maxArea = height * width
			}
		}
		stack.push(i)
	}
	return maxArea
}