84. 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
Link：https://leetcode.com/problems/largest-rectangle-in-histogram/
暴力破解
O(N^2)
从第i个开始, 分别向左右延展，看看以i为高度的长方形面积是多少
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
res = 0
for i in range(len(heights)):
res = max(res, self.calculateMaxArea(heights, i))
return res
def calculateMaxArea(self, heights: List[int], index: int) -> int:
start = end = index
while start - 1 >= 0 and heights[start - 1] >= heights[index]:
start -= 1
while end + 1 < len(heights) and heights[end + 1] >= heights[index]:
end += 1
return (end - start + 1) * heights[index]
单调栈
O(N)
固定高，使用变长来计算最大面积
从左到右扫描，当heights[i]可以被计算面积的时候, 用O来表示
第一个高度是2, 第二个高度是1, 此时O部分的最大面积可以被确定
|
| #
| # #
| # #
| # # #
| # # # # #
| # # # # # #
---------------------------------------
[2, 1, 5, 6, 2, 3]
^
|
| #
| # #
| # #
| # # #
| O # # # #
| O # # # # #
---------------------------------------
[2, 1, 5, 6, 2, 3]
^
left i
第3-4个的时候，面积都无法确认，继续
|
| #
| # #
| # #
| # # #
| O # # # #
| O # # # # #
---------------------------------------
[2, 1, 5, 6, 2, 3]
^ ^
第5个的时候，高度6最大面积可以确认
同时，高度5的面积，也可以确认下来
|
| O
| # O
| # O
| # O #
| O # O # #
| O # # O # #
---------------------------------------
[2, 1, 5, 6, 2, 3]
^
left i
|
| O
| O O
| O O
| O O #
| O O O # #
| O # O O # #
---------------------------------------
[2, 1, 5, 6, 2, 3]
^
left i
后扫描到的，先被计算，满足栈的特点。
同时，还未被计算的高度从小到高，满足单点递增(允许相同的情况)
此时末尾，没有更低的，我们加入一个哨兵-1，来计算剩余部分
代码如下:
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
heights = heights + [-1]
stack = []
res = 0
for i in range(len(heights)):
while stack and heights[stack[-1]] > heights[i]:
index = stack.pop()
left = stack[-1] if stack else -1
area = (i - left - 1) * heights[index]
if res < area:
res = area
stack.append(i)
return res
–End–