难度: Hard
给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4] 输出： 4
提示：
1 <= heights.length <=1050 <= heights[i] <= 104注意：本题与主站 84 题相同： https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
运行时间: 122 ms
内存: 26.3 MB
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
heights.insert(0, 0)
heights.append(0)
stack = [0]
ans = 0
for i in range(1, len(heights)):
if heights[i] > heights[stack[-1]]:
stack.append(i)
elif heights[i] == heights[stack[-1]]:
stack.pop()
stack.append(i)
else:
while heights[stack[-1]] > heights[i]:
top_idx = stack.pop()
left = stack[-1]
width = i - left - 1
ans = max(ans, heights[top_idx] * width)
stack.append(i)
return ans
本题解采用单调栈的方法来解决问题。首先，在数组的开始和结束位置分别添加一个高度为0的柱子，以便处理边界条件。维护一个单调递增的栈，栈中存储的是柱子的索引。遍历输入数组中的每个柱子，当当前柱子的高度大于栈顶元素对应的柱子高度时，直接将当前索引入栈。如果相等，替换栈顶元素。如果当前柱子的高度小于栈顶元素对应的柱子的高度，则持续将栈顶元素弹出，并计算以该栈顶元素为高度的矩形面积，直到栈顶元素的高度小于或等于当前柱子的高度。计算矩形的宽度为当前索引与新的栈顶元素的索引之间的差减一。每次计算完面积后，更新最大面积。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
# 在数组前后添加高度为0的柱子，处理边界条件
heights.insert(0, 0)
heights.append(0)
# 初始化栈，并将第一个元素（高度为0）的索引入栈
stack = [0]
ans = 0
# 遍历所有的柱子
for i in range(1, len(heights)):
# 当前柱子高度大于栈顶柱子高度，直接入栈
if heights[i] > heights[stack[-1]]:
stack.append(i)
# 当前柱子高度等于栈顶柱子高度，替换栈顶
elif heights[i] == heights[stack[-1]]:
stack.pop()
stack.append(i)
# 当前柱子高度小于栈顶柱子高度，计算可能的最大矩形面积
else:
while heights[stack[-1]] > heights[i]:
top_idx = stack.pop()
left = stack[-1]
width = i - left - 1
ans = max(ans, heights[top_idx] * width)
stack.append(i)
return ans
在数组的开始和结束位置添加高度为0的柱子主要是为了简化边界条件的处理。这样做确保了无论柱状图的高度如何变化，所有的柱子都可以在遍历结束时被正确地处理。具体来说，添加在开始位置的0高度柱子保证了栈的初始化状态，而结尾位置的0高度柱子则确保最后一个真正的柱子可以被计算（因为任何大于0的高度都会被弹出处理）。这两个边界柱子作为哨兵，简化了代码逻辑，避免了在循环中对栈空状态的额外检查。
单调递增栈的选择允许我们在遍历时，一旦遇到比栈顶元素小的柱子高度，就可以立即计算以栈顶元素为高度的最大矩形面积。因为在单调递增栈中，每个元素的左边界是确定的，即其前一个元素。这样，当某个高度弹出栈时，我们可以确定这个高度的有效宽度，从而快速计算出以该高度为顶的最大矩形面积。如果使用单调递减栈，则在弹栈时难以确定左边界，因此会增加解题的复杂度。
当当前柱子的高度等于栈顶柱子的高度时，替换栈顶元素的目的是更新可能的最长宽度的起始位置。如果保留原栈顶元素，那么之后计算宽度时会使用错误的起始索引（即更早的索引），这可能导致宽度被错误地延伸，从而计算出错误的面积。替换成当前的索引能确保，如果后续有相同高度的柱子继续处理，它们的宽度计算是基于最新的、正确的起始位置。