0084：柱状图中最大的矩形（★★）

力扣第 84 题

题目

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

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

示例 1:

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

示例 2：

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

提示：

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

分析

• 遍历矩形的底太费时，有个巧妙的想法是遍历矩形的高
• 最大矩形的高度必然是某个柱子的高度
• 于是遍历每根柱子作为高，找左右能延伸的最大宽度即可
• 找左右第一根更矮的柱子，容易想到单调栈
  • 栈 sk 严格递增
  • 遍历到位置 j 且出栈位置 i 时，i 的上一个更小元素即为 sk[-1]
  • 如果 heights[i]>heights[j]，i 的下一个更小元素即为 j，即得到 i 对应的最大宽度
  • 如果 heights[i]==heights[j]，i 和 j 对应的最大宽度相同，可以留给 j 来计算

注意最后栈中可能还有剩余元素，需要遍历计算。一个更简单的做法是在 heights 末尾加一个极小值，让所有元素都出栈。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        res,sk = 0, []
        for j,h in enumerate(heights+[0]):
            while sk and sk[-1][1]>=h:
                _,x = sk.pop()
                i = sk[-1][0] if sk else -1
                res = max(res,x*(j-i-1))
            sk.append((j,h))
        return res

233 ms