Maximal Rectangle 是 LeetCode Hot 100 里面一道非常经典的矩阵题。
这道题第一次看时，很多人都会有点发懵。因为题目给的是一个只包含 0 和 1 的二维矩阵，要求你在其中找到只包含 1 的最大矩形面积。
看起来像是在二维平面上直接找矩形，但如果真的按最直觉的方式去枚举：
-
枚举左上角
-
-
判断这个矩形内部是不是全是
1
那复杂度会非常高，几乎不可能通过。
这道题真正巧妙的地方在于：
它可以转化成很多次“柱状图中最大的矩形”。
而你给出的这份 Java 代码，正是这道题最经典的一种写法：
-
按行扫描矩阵
-
把每一行都转化成一个“柱状图高度数组”
-
对每一行对应的柱状图，求一次最大矩形面积
-
取所有行中的最大值
因为你在前一题已经写了“柱状图中最大的矩形”，所以这道题其实可以理解成：
在二维矩阵上套一层柱状图思想。
本文就结合这段代码，系统地讲一下这道题的思路。
题目介绍
给定一个仅包含 '0' 和 '1' 的二维矩阵 matrix，请你找出其中只包含 1 的最大矩形，并返回其面积。
例如：
matrix =
[
['1','0','1','0','0'],
['1','0','1','1','1'],
['1','1','1','1','1'],
['1','0','0','1','0']
]
在这个矩阵中，最大的只包含 1 的矩形面积是：
6
这道题最难的地方，不是“什么是矩形”，而是：
怎么高效判断某个大矩形是否全是 1，以及如何避免暴力枚举。
示例
示例 1
输入：
matrix =
[
['1','0','1','0','0'],
['1','0','1','1','1'],
['1','1','1','1','1'],
['1','0','0','1','0']
]
输出：6
其中最大的矩形可以是中间那一块连续的 1，面积为 6。
示例 2
输入：matrix = []
输出：0
空矩阵中当然不存在矩形，所以返回 0。
最直接的想法为什么不好？
如果不考虑优化，一个最直接的思路可能是：
-
枚举矩形左上角
-
枚举矩形右下角
-
检查这个矩形区域内是否全部为
1 -
如果是，就更新最大面积
但这种做法的代价非常大，因为：
-
矩形数量很多
-
每个矩形还要检查内部所有元素
所以整体复杂度会高得离谱。
因此，这道题真正高效的关键，不是“暴力找矩形”，而是找到一个更适合计算矩形面积的表示方式。
核心思路：按行构造柱状图
这道题最巧妙的地方就在这里。
我们从第一行开始往下看，把每一列“连续的 1 的高度”记录下来。
例如矩阵：
[
['1','0','1','0','0'],
['1','0','1','1','1'],
['1','1','1','1','1']
]
我们逐行构造高度数组：
第 1 行后
height = [1,0,1,0,0]
第 2 行后
如果当前位置还是 '1'，说明这一列的连续高度可以继续加一； 如果是 '0'，说明连续高度中断，重置为 0。
所以变成：
height = [2,0,2,1,1]
第 3 行后
继续更新：
height = [3,1,3,2,2]
你会发现，这个 height 数组就像是一个柱状图。 而“以当前行为底”的最大只含 1 矩形，恰好就等价于：
这个柱状图中的最大矩形面积。
所以整道题就转化成了：
-
对每一行构造一个柱状图
-
然后调用“柱状图最大矩形”的解法
这正是你代码的整体思路。
Java 代码
下面是你给出的代码，我这里保留原始逻辑，并加上注释：
class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0) return 0;
// height[col] 表示当前行作为底时，第 col 列连续 1 的高度
int[] height = new int[matrix[0].length];
int res = 0;
for (char[] chars : matrix) {
// 更新当前行对应的柱状图高度
for (int col = 0; col < chars.length; col++) {
if (chars[col] == '1') height[col]++;
else height[col] = 0;
}
// 对当前柱状图求最大矩形面积
res = Math.max(res, largesRectangleArea(height));
}
return res;
}
public int largesRectangleArea(int[] heights) {
Stack<Integer> s = new Stack<>();
int[] lefLower = new int[heights.length];
int[] rigLower = new int[heights.length];
Arrays.fill(rigLower, heights.length);
for (int i = 0; i < heights.length; i++) {
while (!s.empty() && heights[s.peek()] > heights[i]) {
rigLower[s.pop()] = i;
}
lefLower[i] = s.empty() ? -1 : s.peek();
s.push(i);
}
int res = 0;
for (int i = 0; i < heights.length; i++) {
res = Math.max(res, (rigLower[i] - lefLower[i] - 1) * heights[i]);
}
return res;
}
}
代码拆解
这段代码其实可以分成两部分来看：
-
maximalRectangle：负责把二维矩阵转成一行行柱状图 -
largesRectangleArea：负责求每个柱状图中的最大矩形
你前一题已经写过柱状图最大矩形，所以这题的真正重点，其实是第一部分——如何把二维问题转化成一维柱状图问题。
1. 为什么空矩阵直接返回 0？
if (matrix.length == 0) return 0;
因为如果矩阵没有任何行，那自然不可能形成矩形，答案就是 0。
这是一个基础边界情况，必须先处理掉。
2. height 数组表示什么？
int[] height = new int[matrix[0].length];
这个数组非常关键。
它表示：
当前这一行作为矩形底边时，每一列往上连续有多少个 1。
也就是说：
-
如果当前列这一格是
'1'，那么高度可以在上一行的基础上继续加 1 -
如果当前列这一格是
'0'，说明连续性被打断，这一列高度重置为 0
这个高度数组，就是我们把二维矩阵压缩成柱状图的桥梁。
3. 为什么更新高度时是这样写？
for (int col = 0; col < chars.length; col++) {
if (chars[col] == '1') height[col]++;
else height[col] = 0;
}
因为我们是逐行往下扫描的。
假设当前处理到第 r 行，那么：
-
如果
matrix[r][col] == '1'-
说明这一列在当前行仍然可以和上面的连续
1连起来 -
所以
height[col]++
-
-
如果
matrix[r][col] == '0'-
说明连续高度中断
-
所以
height[col] = 0
-
这就是为什么它能够构造出“以当前行为底”的柱状图。
4. 为什么每一行更新完 height 后，就可以求一次最大矩形？
res = Math.max(res, largesRectangleArea(height));
因为当你固定“当前行”为矩形的底边时，height 数组就完整描述了：
每一列往上最多能延伸多高。
而任何一个只包含 1 的矩形，只要它的底边落在当前行，那么它一定可以在这个柱状图中对应成一个矩形。
所以：
-
当前行更新出一个柱状图
-
在这个柱状图里求最大矩形
-
就等于求“以当前行为底的最大只含 1 的矩形”
把所有行都处理一遍，取最大值，就是整个矩阵中的答案。
5. largesRectangleArea 在做什么？
这一部分其实就是上一题“柱状图中最大的矩形”的标准写法。
它的核心思想是：
-
对每个柱子，找到左边第一个更小的位置
-
找到右边第一个更小的位置
-
于是当前柱子作为最低高度时的最大宽度就确定了
-
面积公式为：
(右边界 - 左边界 - 1) × 当前高度
这里我不再展开重复上一题的全部推导，但可以简单强调一下：
lefLower[i]
表示左边第一个比 heights[i] 更小的位置
rigLower[i]
表示右边第一个比 heights[i] 更小的位置
然后面积就是：
(rigLower[i] - lefLower[i] - 1) * heights[i]
这一步本质上就是把当前 height 当作柱状图来求解。
手动模拟一遍
我们用经典样例来走一下：
matrix =
[
['1','0','1','0','0'],
['1','0','1','1','1'],
['1','1','1','1','1'],
['1','0','0','1','0']
]
第 1 行
更新后：
height = [1,0,1,0,0]
这是一个柱状图。 它的最大矩形面积是：
1
第 2 行
更新后：
height = [2,0,2,1,1]
对应柱状图最大矩形面积是：
3
比如右边三个柱子 [2,1,1] 可以形成高为 1、宽为 3 的矩形。
第 3 行
更新后：
height = [3,1,3,2,2]
这时柱状图最大矩形面积变成：
6
例如柱子 [3,2,2] 中，以高度 2 扩展宽度 3，可以形成：
2 × 3 = 6
这也正是整个矩阵的最终答案。
第 4 行
更新后：
height = [4,0,0,3,0]
这一行对应的柱状图最大矩形面积不会超过前面的 6，所以最终答案仍然保持为 6。
为什么这个方法是正确的？
因为矩阵中的任意一个全 1 矩形，都一定有一个“底边所在行”。
当我们扫描到这条底边所在行时：
-
这个矩形覆盖到的每一列，其连续 1 的高度一定至少等于这个矩形的高度
-
所以它一定会出现在当前构造出来的柱状图中
-
而柱状图最大矩形算法一定不会漏掉它
换句话说：
-
每个二维矩形，都能在某一行对应成柱状图问题中的一个矩形
-
我们对每一行都求一次柱状图最大矩形
-
因此最终一定能覆盖所有可能答案
这就说明这种“矩阵转柱状图”的方法是完全正确的。
复杂度分析
假设矩阵大小为：
m × n
时间复杂度
对于每一行：
-
更新
height数组需要O(n) -
调用一次柱状图最大矩形也需要
O(n)
所以每一行总共是：
O(n)
一共有 m 行，因此总时间复杂度是：
O(m × n)
空间复杂度
额外使用了：
-
一个
height数组 -
柱状图解法里用到的栈和左右边界数组
所以整体额外空间复杂度是：
O(n)
这道题真正想考什么？
这道题表面上是在二维矩阵里找最大矩形，但本质上考察的是两个非常重要的能力。
第一，能不能把二维问题转化成一维问题
这是整道题最精华的地方。
如果你一直停留在“二维枚举矩形”的思路里，这题会非常难。 但一旦想到“按行压缩成柱状图”，问题立刻就清晰很多。
第二，是否掌握柱状图最大矩形这个模板
这题本质上是上一题的进阶应用。 如果你已经理解了柱状图中最大矩形，那么这题真正新增的内容只剩下：
-
怎么构造
height -
为什么构造出来后就能套模板
所以这两题通常都是连着刷的。
和“柱状图中最大的矩形”有什么关系？
这两题的关系非常直接。
柱状图中最大的矩形
给你一个一维高度数组，求最大矩形。
最大矩形
给你一个二维 0/1 矩阵，每一行都可以压成一个柱状图，然后对每一行调用上一题的解法。
所以这道题几乎可以看成：
柱状图最大矩形模板的二维应用版。
也正因为如此，这题非常适合在写博客时和上一题连起来讲。
总结
这道题的核心思想可以概括成一句话：
把矩阵按行扫描，并把每一行看成一个柱状图的底边，维护每列连续 1 的高度，然后对每一行调用“柱状图中最大的矩形”算法。
具体步骤就是：
-
开一个
height数组，记录当前行作为底时每列连续 1 的高度 -
逐行扫描矩阵：
-
如果当前位置是
1，高度加一 -
如果是
0，高度清零
-
-
每更新完一行，就把当前
height当作柱状图，求一次最大矩形 -
在所有行中取最大值
这样就能在：
O(m × n)
的时间复杂度下解决问题。
这是一道非常经典、也非常值得反复理解的题。 因为它会让你真正体会到：
-
二维问题如何降维
-
模板题之间是如何串联起来的
-
单调栈为什么在矩形类题目中这么强大
把这道题真正吃透之后，再去看：
-
接雨水
-
柱状图中最大的矩形
-
最大正方形
-
岛屿类矩阵题
你会更容易意识到： 很多看起来复杂的二维题，其实关键往往是能不能找到一个合适的一维表示方式。
