难度: Hard
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4] 输出： 4
提示：
1 <= heights.length <=1050 <= heights[i] <= 104
Submission
运行时间: 104 ms
内存: 0.0 MB
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
indices_stack = []
area = 0
for index, height in enumerate(heights + [0]):
while indices_stack and heights[indices_stack[-1]] >= height: #如果列表尾部高度大于当前高度
popped_index = indices_stack.pop()
left_index = indices_stack[-1] if indices_stack else -1
#如果列表为空(即h[i]左边没有比它小的数)，则宽度为index，否则为index-indices_stack[-1]-1
width = index - left_index - 1
area = max(area, width * heights[popped_index])
indices_stack.append(index) #压入列表中
return area
Explain
本题解使用单调栈的方法来解决柱状图中最大矩形面积的问题。具体思路如下： 1. 维护一个单调递增的栈，栈中存储柱子的索引。 2. 遍历柱子高度数组，对于每个柱子： - 如果当前柱子的高度小于栈顶索引对应的柱子高度，则持续出栈，直到栈为空或者栈顶柱子高度小于当前柱子高度。 - 对于每个出栈的柱子，计算以其高度为矩形高度的最大矩形面积，更新最大面积。 - 将当前柱子的索引入栈。 3. 返回最大矩形面积。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
indices_stack = []
area = 0
# 在高度数组末尾添加一个高度为0的柱子，确保所有柱子都会被处理
for index, height in enumerate(heights + [0]):
# 如果栈非空且当前柱子的高度小于栈顶索引对应的柱子高度
while indices_stack and heights[indices_stack[-1]] >= height:
# 出栈，直到栈为空或者栈顶柱子高度小于当前柱子高度
popped_index = indices_stack.pop()
# 计算左侧边界的索引
left_index = indices_stack[-1] if indices_stack else -1
# 计算矩形的宽度
width = index - left_index - 1
# 更新最大矩形面积
area = max(area, width * heights[popped_index])
# 将当前柱子的索引入栈
indices_stack.append(index)
return area
Explore
在数组末尾添加一个高度为0的柱子的主要目的是确保所有在栈中的柱子都能被完全处理。这样做可以触发栈中所有剩余柱子的出栈操作，因为0比任何正高度都小，这保证了在遍历结束时栈为空，使得算法能够计算出所有可能的矩形面积并找到最大值。
当栈中所有元素被弹出后，新的栈顶元素的索引会是下一个在栈中的元素索引。如果栈变为空，则意味着当前弹出的柱子左侧没有更低的柱子，因此左侧边界被设为-1。这个索引对最大面积的计算至关重要，因为它帮助确定了柱子的宽度。如果栈为空，说明当前柱子左侧没有更小的柱子，其宽度可以扩展到整个数组的起始位置。
单调递增栈被选用是因为它可以在遇到一个较小的元素时，方便地处理所有在栈中并且高度高于当前元素的柱子。这样可以立即计算出以这些柱子为高度的最大矩形面积。使用单调递减栈也可以解决问题，但处理逻辑略有不同，主要是在处理矩形宽度时需要更多的考虑，例如延伸到更远的右边界。因此，单调递增栈在逻辑上更直接和简洁。
公式中的'减1'是因为需要排除当前处理的柱子本身。'index'是当前柱子的索引，而'left_index'是上一个在栈中且高度小于当前柱子的索引。因此，实际的可用宽度是从'left_index + 1'到'index - 1'。例如，若'left_index'为2且'index'为5，那么宽度应为5 - 2 - 1 = 2，即索引为3和4的两根柱子。