LeetCode 85. 最大矩形
题目描述
✅ 85. 最大矩形
题意分析
在一个只包含字符
'0'和'1'的矩阵中，找出内部全部为'1'的最大矩形，返回面积。矩形由连续的若干行和连续的若干列组成，不能跳过中间的零，也不要求它是正方形。面积由高度与宽度共同决定。每个候选矩形都有一条确定的底边，因此可以逐行把当前行当作底边，寻找在这条底边上能够形成的最大矩形，再取全局最大值。
解法：逐行转柱状图 + 单调栈
核心思路
[!blue]
用
heights[col]记录以当前行为底、该列向上连续出现'1'的数量。当前格为'1'就在上一行高度上加一，为'0'就清零，因为矩形不能跨过这个零。这样每一行都会形成一幅柱状图。在若干连续列之间，矩形能取的高度不超过这些列的最小柱高。因此，当前行作为底边的最大全一矩形，正是这幅柱状图的最大矩形。反过来，原矩阵中的每个矩形都属于其底边对应的某一行，逐行求解不会漏掉全局最优答案。
对柱状图，用栈保存尚未结算完的柱子下标，保持下标递增、对应高度严格递增。遇到高度更大的柱子时先入栈，因为之前较矮的柱子仍可向右延伸。遇到不高于栈顶的柱子，就不断弹出栈顶，结算以被弹柱高
height为高度的一段矩形。弹出后，设新栈顶为
left，栈空时令left = -1。它是被弹柱左侧的严格更矮边界，而从left + 1到当前下标i - 1的柱子都不低于height，所以可以计算面积height * (i - left - 1)。栈里保存下标，正是为了通过这两个位置算出宽度。本实现遇到相等高度也弹栈。此时
i只是本次结算的右端外边界，并不表示这个高度已经无法继续向右延伸；随后入栈的新下标会接替旧柱，并保留向左跨过这段等高区域的能力。更宽的同高矩形会由新代表在后面结算，因此不会漏掉答案，也不能把所有弹栈都解释成遇到了严格更矮的右边界。扫描完真实柱子后，再处理一根虚拟高度为
0的柱子，统一结算栈中剩余候选。代码最后把虚拟下标入栈后就结束循环，不会用它访问真实的高度数组。
解题步骤
- 先处理空矩阵边界，创建长度为列数的高度数组和全局答案。
- 逐行更新高度：当前格为
'1'则加一，否则清零。- 对当前高度数组创建空栈，从下标
0扫描到虚拟末尾下标n，虚拟高度为零。- 当前高度不大于栈顶高度时持续弹栈，用弹出高度和新栈顶确定左边界，更新面积
height * (i - left - 1)。- 清理后把当前下标入栈。将这幅柱状图的最大面积合入全局答案，继续下一行。
代码实现
class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int[] heights = new int[matrix[0].length];
int ans = 0;
for (char[] row : matrix) {
for (int col = 0; col < row.length; col++) {
// 高度是以当前行为底的连续一，遇零必须重新归零。
heights[col] = row[col] == '1' ? heights[col] + 1 : 0;
}
ans = Math.max(ans, largestRectangleArea(heights));
}
return ans;
}
private int largestRectangleArea(int[] heights) {
int[] stack = new int[heights.length + 1];
int top = -1;
int ans = 0;
for (int i = 0; i <= heights.length; i++) {
int current = i == heights.length ? 0 : heights[i];
while (top >= 0 && heights[stack[top]] >= current) {
int height = heights[stack[top--]];
// 弹出候选柱后，新栈顶是左界；i 处高度不大于候选高度，是本次结算的右界。
int left = top >= 0 ? stack[top] : -1;
ans = Math.max(ans, height * (i - left - 1));
}
stack[++top] = i;
}
return ans;
}
}
func maximalRectangle(matrix [][]byte) int {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return 0
}
heights := make([]int, len(matrix[0]))
ans := 0
for _, row := range matrix {
for col := range row {
if row[col] == '1' {
heights[col]++
} else {
// 遇零就断开这一列的连续高度，不能跨过零累加。
heights[col] = 0
}
}
if area := largestRectangleArea(heights); area > ans {
ans = area
}
}
return ans
}
func largestRectangleArea(heights []int) int {
stack := make([]int, 0, len(heights)+1)
ans := 0
for i := 0; i <= len(heights); i++ {
current := 0
if i < len(heights) {
current = heights[i]
}
for len(stack) > 0 && heights[stack[len(stack)-1]] >= current {
height := heights[stack[len(stack)-1]]
stack = stack[:len(stack)-1]
left := -1
if len(stack) > 0 {
left = stack[len(stack)-1]
}
// 左右界都不包含在当前矩形中，宽度取中间位置数。
if area := height * (i - left - 1); area > ans {
ans = area
}
}
stack = append(stack, i)
}
return ans
}
复杂度分析
- 时间复杂度：$O(mn)$，其中
m、n为行数和列数。每行更新高度需要 $O(n)$；栈中每个下标至多入栈、出栈一次，求柱状图面积也为 $O(n)$。- 空间复杂度：$O(n)$，保存一行高度和本行的单调栈，无需保存每一行的历史高度。
关键点总结
[!green]
- 逐行枚举底边，连续一的高度把二维矩形转换为柱状图矩形。
- 栈维护的是候选下标，弹出后用新栈顶和当前扫描下标计算可用宽度。
>=弹栈使高度严格递增，等高旧柱的后续扩展机会交给更新的同高柱。- 虚拟零柱统一结算仍留在栈中的候选，不需要单独编写收尾循环。
易错点总结
[!yellow]
- 输入是字符矩阵，应比较字符
'1'，不能用整数1代替。- 遇零后必须把当前列高度清零，否则会把不连续的两段一接在一起。
- 宽度为
i - left - 1，因为计算的区间不包含两侧边界；不能直接用两个下标之差。- 把等高弹栈说成最终的最大扩展范围，会与代码不符；同高更宽的候选留给当前柱继续处理。
- 不处理末尾虚拟零柱，右侧一直递增的候选会留在栈中，可能遗漏最大面积。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 84. 柱状图中最大的矩形 | 困难 | 逐行维护连续1的高度后，每一行直接转为柱状图最大矩形。 |
| 907. 子数组的最小值之和 | 中等 | 用单调栈确定元素能影响的连续区间边界；本题逐行累计柱高并复用直方图算法，该题统计每个值作为区间最小值的贡献。 |