给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10示例 2：
输入： heights = [2,4]
输出： 4暴力求解：会超时
# [84] 柱状图中最大的矩形
#
# @lc code=start
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
maxs=0
for i in range(len(heights)):
for j in range(i,len(heights)):
ms=min(heights[i:j+1])
maxs=max(maxs,ms*(j-i+1))
return maxs
# @lc code=end使用栈求解：
- 首先我们枚举某一根柱子 i 作为高 h=heights[i]；
- 随后我们需要进行向左右两边扩展，使得扩展到的柱子的高度均不小于 h。换句话说，我们需要找到左右两侧最近的高度小于 h 的柱子，这样这两根柱子之间（不包括其本身）的所有柱子高度均不小于 h，并且就是 i 能够扩展到的最远范围。
我们用一个具体的例子 [6, 7, 5, 2, 4, 5, 9, 3] 来帮助读者理解单调栈。我们需要求出每一根柱子的左侧且最近的小于其高度的柱子。初始时的栈为空。
- 我们枚举 6，因为栈为空，所以 6 左侧的柱子是「哨兵」，位置为 -1。随后我们将 6 入栈。
- 栈：
[6(0)]。（这里括号内的数字表示柱子在原数组中的位置）
- 栈：
- 我们枚举 7，由于 6<7，因此不会移除栈顶元素，所以 7 左侧的柱子是 6，位置为 0。随后我们将 7 入栈。
- 栈：
[6(0), 7(1)]
- 栈：
- 我们枚举 5，由于 7≥5，因此移除栈顶元素 7。同样地，6≥5，再移除栈顶元素 6。此时栈为空，所以 5 左侧的柱子是「哨兵」，位置为 −1。随后我们将 5 入栈。
- 栈：
[5(2)]
- 栈：
- 接下来的枚举过程也大同小异。我们枚举 2，移除栈顶元素 5，得到 2 左侧的柱子是「哨兵」，位置为 −1。将 2 入栈。
- 栈：
[2(3)]
- 栈：
- 我们枚举4，5 和 9，都不会移除任何栈顶元素，得到它们左侧的柱子分别是 2，4 和 5，位置分别为 3，4 和 5。将它们入栈。
- 栈：
[2(3), 4(4), 5(5), 9(6)]
- 栈：
- 我们枚举 3，依次移除栈顶元素 9，5 和 4，得到 3 左侧的柱子是 2，位置为 3。将 3 入栈。
- 栈：
[2(3), 3(7)]
- 栈：
这样以来，我们得到它们左侧的柱子编号分别为 [-1, 0, -1, -1, 3, 4, 5, 3]。用相同的方法，我们从右向左进行遍历，也可以得到它们右侧的柱子编号分别为 [2, 2, 3, 8, 7, 7, 7, 8]，这里我们将位置 8 看作「哨兵」。
在得到了左右两侧的柱子之后，我们就可以计算出每根柱子对应的左右边界，并求出答案了。
# @lc code=start
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
# maxs=0
# for i in range(len(heights)):
# for j in range(i,len(heights)):
# ms=min(heights[i:j+1])
# maxs=max(maxs,ms*(j-i+1))
# return maxs
n = len(heights)
left, right = [0] * n, [0] * n
mono_stack = list()
for i in range(n):
while mono_stack and heights[mono_stack[-1]] >= heights[i]:
mono_stack.pop()
left[i] = mono_stack[-1] if mono_stack else -1
mono_stack.append(i)
mono_stack = list()
for i in range(n - 1, -1, -1):
while mono_stack and heights[mono_stack[-1]] >= heights[i]:
mono_stack.pop()
right[i] = mono_stack[-1] if mono_stack else n
mono_stack.append(i)
ans = max((right[i] - left[i] - 1) * heights[i] for i in range(n)) if n > 0 else 0
return ans