Largest Rectangle in Histogram
直方图是一排并排排列、彼此之间没有间隙的柱子，每根柱子的宽度都是 1：heights[i] 表示第 i 根柱子的高度。直方图中的矩形覆盖一段相邻的柱子，其高度不能超过这段柱子中最矮的那根。
返回这样的矩形所能达到的最大面积。
函数
- heightsinteger-array
- 每个柱子的高度，从左到右
- 返回值integer
- 直方图中能容纳的最大矩形的面积
约束条件
1 ≤ heights.length ≤ 2 × 1040 ≤ heights[i] ≤ 105- 每根柱子的宽度都是 1 个单位，因此覆盖从
i到j的柱子的矩形宽度为j-i+1个单位。
示例
- 输入
- heights = [2, 5, 6, 3, 4, 1]
- 输出
- 12
- 解释
- 高度为 5、6、3 和 4 的柱子都至少有 3 高，因此可以跨越它们构成一个高度为 3 的矩形：3 × 4 = 12。最高的两根柱子只能构成 5 × 2 = 10。
- 输入
- heights = [1, 8, 1, 1]
- 输出
- 8
- 解释
- 单独的 8 这一条宽度为 8，因此 8 × 1 = 8。任何更宽的长方形都包含一条宽度为 1 的条，因此其面积最大为 1 × 4 = 4。
- 输入
- heights = [3, 3, 3, 3]
- 输出
- 12
- 解释
- 这 4 根柱子的高度都是 3，所以整个直方图是一个矩形：3 × 4 = 12。
进阶
假设每根柱子都有自己的宽度，这些宽度存放在第二个数组中。那么，单次遍历的栈解法需要做哪些改动？
提示
逐个打开提示，每个都会多透露一点。
最大的矩形会接触下方至少一根柱子的顶部：如果没有接触，你就可以把它变得更高。因此，尝试让每根柱子都作为确定高度的柱子。恰好这么高的矩形最多能有多宽？
一个高度与柱子
i相同的矩形会向左右延伸，直到两侧分别遇到严格更矮的柱子。如果你知道每根柱子两侧最近的更矮柱子，那么每根柱子都会对应一个候选面积，总共只有n个。维护一个索引栈，栈中柱子的高度从栈底到栈顶递增。当遇到的柱子高度不大于栈顶柱子的高度时，栈顶柱子无法再向右延伸：将它弹出，它对应的矩形覆盖新栈顶与当前柱子之间的柱子。一根高度为 0 的柱子放在末尾，用来弹出栈中剩余的所有柱子。
题解
遍历每一段连续柱子大约需要 n²/2 步。换个思路：最大矩形的高度正好等于其中一根柱子的高度，因此每根柱子只需要知道自己能延伸多远，直到被更矮的柱子挡住。单调栈可以在 O(n) 内找到这些位置。
每次运行时都尝试记录当前最小值
结果正确，但无法在最大的测试中运行完毕
思路
固定 start，每次将 end 向右移动一根柱子，并记录目前为止见过的最低高度。这段范围内的最大矩形面积是 lowest × (end-start+1)。从 [2, 5, 6, 3, 4, 1] 中的 5 开始，这些范围的面积分别是 5、10、9、12 和 5。
这种方法是正确的，因为每个矩形都覆盖某段范围，而且高度不会超过这段范围内最低柱子的高度。但它很慢，因为共有 n(n+1)/2 段范围：对于 2 × 10^4 根柱子，大约有 2 × 10^8 段。
算法
- 将
best设为 0。 - 对于每个
start，将lowest设为heights[start]。 - 对于从
start到最后一根柱子的每个end，如果该柱子更矮，就将lowest降低为heights[end]。 - 用
lowest × (end-start+1)更新best。 - 返回
best。
def largestRectangleArea(heights):
n = len(heights)
best = 0
for start in range(n):
lowest = heights[start]
for end in range(start, n):
# The rectangle over start..end is as tall as the lowest bar in it.
lowest = min(lowest, heights[end])
best = max(best, lowest * (end - start + 1))
return best两侧最近的较短柱
思路
最大的矩形会到达至少一根柱子的顶部，否则你还可以将它抬高。因此，对于每根柱子 i，取一个高度恰好为 heights[i] 的矩形，并让它向两侧延伸，直到遇到更矮的柱子，位置分别为 left[i] 和 right[i]（如果不存在，则分别为 -1 和 n）。矩形的宽度为 right[i]-left[i]-1。
要找到 left[i]，从左向右遍历，并用一个存储索引的栈，使栈中对应的柱子高度递增。柱子 i 会弹出所有高度大于或等于自身的柱子：它们都不可能是 i 或之后任何柱子最近的更矮柱子，因为 i 更近，而且高度不更高。此时栈顶就是 left[i]。从右向左遍历即可得到 right[i]。
每个索引在每次遍历中最多入栈和出栈一次，因此时间复杂度为 O(n)。
算法
- 用栈从左向右遍历。对于每个
i，当栈顶柱子的高度大于或等于heights[i]时，将其弹出；如果栈不为空，将栈顶设为left[i]，否则设为 -1；然后将i入栈。 - 同样地，从右向左遍历，求
right[i]；如果栈为空，则设为n。 - 返回最大的
heights[i] × (right[i]-left[i]-1)。
def largestRectangleArea(heights):
n = len(heights)
left = [-1] * n # index of the nearest shorter bar on the left, or -1
right = [n] * n # index of the nearest shorter bar on the right, or n
stack = [] # indices whose heights rise strictly from bottom to top
for i in range(n):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
if stack:
left[i] = stack[-1]
stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
if stack:
right[i] = stack[-1]
stack.append(i)
best = 0
for i in range(n):
# Bar i is the lowest bar of everything strictly between left[i] and right[i].
best = max(best, heights[i] * (right[i] - left[i] - 1))
return best使用单调栈进行一次遍历
思路
从左向右扫描时，每根柱子的右边界都已满足，但这个信息被丢弃了。当柱子 i 弹出柱子 t 时，柱子 i 不比它高，因此柱子 t 的矩形在这里结束。它的左边界是 below，也就是此时栈中位于 t 下方的索引；如果栈为空，则是 -1。在弹出时计算面积：heights[t] × (i - below - 1)。
这个左边界是正确的，因为从某个元素到它下方元素之间的每根柱子，都已被该元素直接或通过一连串弹出操作弹出，所以没有一根比该元素矮。高度为 0 的收尾柱子会弹出剩余的柱子。在第一个示例中，索引 5 处高度为 1 的柱子会弹出索引 3 处高度为 3 的柱子，其下方是索引 0：3 × 4 = 12。
提前弹出高度相同的柱子是安全的：后面的柱子会继承它的左边界，并计算整个连续区间的面积。
算法
- 从一个空栈开始，并设置
best = 0。 - 让
i从 0 到n，取高度heights[i]；当i = n时，取 0。 - 当栈顶柱子的高度大于或等于该高度时，将其弹出并记为
t，然后用heights[t] × (i - below - 1)更新best，其中below是新的栈顶，若栈为空则为 -1。 - 将
i入栈。 - 返回
best。
def largestRectangleArea(heights):
n = len(heights)
stack = [] # indices whose heights rise strictly from bottom to top
best = 0
for i in range(n + 1):
current = heights[i] if i < n else 0 # a bar of 0 past the end empties the stack
while stack and heights[stack[-1]] >= current:
# Bar i stops the popped bar on the right; the bar below it stops it on the left.
height = heights[stack.pop()]
left = stack[-1] if stack else -1
best = max(best, height * (i - left - 1))
stack.append(i)
return best
易错点和边界情况
- 忘记了栈中仍然存在的柱子。在
[1, 2, 3, 4, 5]中，循环内没有弹出任何柱子；如果没有末尾的 0，返回值会是 0，而不是 9。 - 从弹出柱子自身的索引开始计算宽度。在第一个示例中，索引 3 处高度为 3 的柱子横跨索引 1 到 4；
i - t得到的是 2，而不是 4。 - 弹出后栈为空时，宽度计算错误。此时宽度是
i：在[2, 1, 2]中，高度为 1 的柱子横跨全部 3 根柱子，面积为 3。 - 两遍处理的版本中只在
>时弹出。在[3, 3, 3, 3]中，这样每根柱子的宽度都会是 1，返回值会是 3，而不是 12。
常见问题3
柱状图中最大矩形的时间复杂度是多少？
单调栈解法的时间复杂度为 O(n)，额外空间复杂度为 O(n)：每个索引只会入栈一次、出栈一次。遍历每一段连续的柱形需要 O(n²) 的时间。
能用分治法解决直方图中的最大矩形问题吗？
是的。一个范围内的最低柱，要么位于最佳矩形下方，此时矩形面积为 lowest × width；要么将范围分成两部分，分别求解。扫描查找最小值时，随机输入下的时间复杂度为 O(n log n)，已排序输入下为 O(n²)；使用线段树则始终为 O(n log n)。
直方图中的最大矩形如何用于 0/1 网格中的最大矩形？
逐行遍历，按列统计截至当前行连续出现的 1 的数量；遇到 0 就将计数重置为 0。每行的计数组成一个直方图，而其中的最大矩形就是以该行为底边的全 1 最大矩形：总时间复杂度为 O(rows × cols)。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def largestRectangleArea(heights):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
heights = [2, 5, 6, 3, 4, 1]
预期输出
12