LeetCode 85. 最大矩形
目录
题目描述
✅ 85. 最大矩形
题意分析
给一个只含字符
'0'和'1'的二维矩阵，要在其中找出一块全部由 1 组成的轴对齐矩形，返回它的最大面积。注意矩形必须是连续的整块区域，不能是若干散落 1 的集合，也不能斜着放。题面给的是字符矩阵而不是整数矩阵，比较时要写
'1'而不是1，这是最容易被忽略的一个信号。规模上行列数最多各 200，元素总量四万，说明 $O(mn)$ 到 $O(mn\log n)$ 的做法都很宽裕，但穷举所有矩形的 $O(m^2n^2)$ 会明显偏慢。边界要考虑：矩阵可能为空或某一行为空，此时答案为 0；矩阵中可能一个 1 都没有，答案同样是 0；只有单行或单列时答案退化成最长连续 1 的长度；全 1 矩阵时答案是整个矩阵面积。
解法：逐行转柱状图 + 单调栈
核心思路
任何全 1 矩形都有一条确定的底边。逐行枚举底边，并令
heights[j]表示以当前行为底、第j列向上连续 1 的数量：
heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0固定底边后，矩阵问题就等价于柱状图最大矩形：选择一段连续列，能取得的高度是区间内最矮柱子的高度。这样每行调用一次第 84 题的单调栈算法即可覆盖所有候选矩形。
柱状图中维护下标栈，并保持对应高度严格递增。当当前高度小于栈顶时，当前位置
i是栈顶柱子右侧第一个更矮的位置，弹栈后的新栈顶是左侧第一个更矮的位置left，其最大宽度就是i-left-1。为维持严格递增，遇到等高柱也弹出旧下标，再由当前下标接替；旧下标此时只结算一个候选面积，接替者会保留向右扩展的机会，因此不会漏掉等高区间的最大宽度。在末尾追加一个高度为 0 的虚拟柱，强制结算栈内剩余元素。正确性来自两点：每个矩阵矩形都会在其底边那一行对应为一个柱状图矩形；每个柱状图矩形又会在其最矮柱子弹栈时被计算，因此不会漏掉最优解。
解题步骤
- 空矩阵或空行直接返回 0。
- 创建长度为列数的
heights，逐行更新：遇到'1'加一，遇到'0'清零。- 每更新完一行，就对
heights求一次柱状图最大矩形。- 柱状图遍历到
n（含虚拟哨兵）；当前高度不大于栈顶时持续弹栈。- 弹出高度
height后，以新栈顶或-1作为左边界，计算height * (i-left-1)。- 所有行的最大值就是答案。
示例矩阵逐行形成的高度分别为
[1,0,1,0,0]、[2,0,2,1,1]、[3,1,3,2,2]、[4,0,0,3,0]；各行最大面积为 1、3、6、4，所以最终答案为 6。
代码实现
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--]];
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)$。每行更新高度需要 $O(n)$；单调栈中每个下标至多入栈、出栈各一次，也是 $O(n)$。
- 空间复杂度：$O(n)$，用于高度数组和单调栈。
关键点总结
- 按底边逐行压缩，把二维最大全 1 矩形化为多个柱状图问题。
heights[j]只表示“以当前行为底”的连续高度，遇到 0 必须清零。- 单调栈保存下标而非高度，弹栈后才能通过左右边界计算宽度。
- 末尾 0 哨兵统一完成收尾；采用
>=弹栈时，栈内高度保持严格递增。
易错点总结
- 字符矩阵应比较
'1'，不是整数1。- 遇到
'0'不清零会把被 0 隔断的两段 1 错误连接，例如单列1,0,1。- 不加入末尾哨兵时，递增高度
[1,2,3]会留在栈中得不到结算。- 宽度是
i-left-1；左右两个更矮位置本身不能包含在矩形中。- 空矩阵必须在访问
matrix[0]前判断，否则会越界。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 84. 柱状图中最大的矩形 | 困难 | 单调栈的一维原型，本题正是把每一行化归到它 |
| 1504. 统计全 1 子矩形 | 中等 | 同样逐行压高度，但要用单调栈累计子矩形个数而非取最大面积 |
| LCR 039. 柱状图中最大的矩形 | 困难 | 84 题的同题异号版本，可直接复用同一份单调栈模板 |
| LCR 040. 最大矩形 | 困难 | 本题的同题异号版本，输入改为字符串数组，注意按行取字符 |
| 补充题 3. 求区间最小数乘区间和的最大值 | 困难 | 区间贡献从「最小值乘长度」换成「最小值乘区间和」，需配前缀和 |