柱状图中最大的矩形
Largest Rectangle in Histogram
本机进度仅保存在当前浏览器
题目描述
给定 n 个非负整数表示柱状图中各柱子的高度，每根柱子宽度为 1，求在该柱状图中能够勾勒出来的矩形的最大面积。
示例：heights = [2, 1, 5, 6, 2, 3]，最大矩形取高度 5、6 两柱，宽 2，面积 10。
解题思路
- 换个角度：枚举"以每根柱子为最矮柱"能向左右扩展多远，面积 = 高度 × 扩展宽度。
- 朴素扩展是 O(n^2)；单调递增栈在"遇到更矮柱"时一次性确定栈顶柱的左右边界。
- 弹出栈顶时：右边界是当前下标 i，左边界是弹出后新栈顶（其右边第一个更矮柱），宽度为 i - new_top - 1。
- 末尾追加哨兵高度 0，保证所有柱子都被弹出结算；左右相等高度的情况不影响正确性。
参考实现
查看参考实现Python · 建议先自行作答
def largestRectangleArea(heights):
# 哨兵：末尾高度 0 触发全部出栈结算
stack = []
best = 0
for i, h in enumerate(heights + [0]):
while stack and heights[stack[-1]] >= h:
height = heights[stack.pop()]
left = stack[-1] if stack else -1
best = max(best, height * (i - left - 1))
stack.append(i)
return best