题目描述
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
示例分析
示例 1
输入:
matrix = [
['1','0','1','0','0'],
['1','0','1','1','1'],
['1','1','1','1','1'],
['1','0','0','1','0']
]
输出: 4
解释：
最大的只包含 '1' 的正方形是：
1 1
1 1
边长为 2，所以面积为：
2 * 2 = 4
示例 2
输入: matrix = [['0','1'],['1','0']]
输出: 1
因为任意 2 x 2 的区域都无法全部由 '1' 组成，所以最大正方形边长只能是 1。
解题思路
这道题一看就很适合用动态规划。
因为对于矩阵中的某个位置 (i, j) 来说：
-
如果它是
'0'，那它不可能作为正方形的右下角 -
如果它是
'1'，那么它能构成多大的正方形，就取决于它左边、上边、左上角这三个位置能构成多大的正方形
你给出的代码正是这道题非常经典的写法：动态规划 + 一维数组空间优化。
二维 DP 的核心定义
我们先从最容易理解的二维 DP 讲起。
设：
dp[i][j]
表示：
以位置
(i, j)作为右下角时，所能构成的最大全 1 正方形的边长。
为什么是“右下角”？
因为这样定义后，当前位置能否扩成更大的正方形，就可以自然地由它左边、上边、左上角三个位置推出来。
状态转移为什么看三个方向
如果 matrix[i][j] == '1'，那么要想让当前位置成为边长更大的正方形右下角，必须满足：
-
左边也能支撑一个正方形
-
上边也能支撑一个正方形
-
左上角也能支撑一个正方形
只要这三个方向中有一个不够大，当前正方形就扩不起来。
所以状态转移方程就是：
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
其中：
-
dp[i][j - 1]：左边 -
dp[i - 1][j]：上边 -
dp[i - 1][j - 1]：左上角
为什么取最小值？
因为正方形要扩展，三边必须同时满足要求。 真正限制当前边长的，永远是这三个值里最小的那个。
举个例子理解
假设当前位置是 '1'，并且：
左边 = 3
上边 = 2
左上 = 3
那么当前位置最多只能构成边长为：
min(3, 2, 3) + 1 = 3
因为上边只能支撑到 2，所以就算左边和左上都够大，当前也不可能扩成边长为 4 的正方形。
这就是为什么一定要取三者最小值。
你的代码为什么只用一维 dp
你给出的代码没有开二维数组，而是把二维 DP 压缩成了一维。
代码如下：
class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length < 1 || matrix[0].length < 1) return 0;
int height = matrix.length;
int width = matrix[0].length;
int maxSide = 0;
int[] dp = new int[width + 1];
for (char[] chars : matrix) {
int northwest = 0;
for (int col = 0; col < width; col++) {
int nextNorthwest = dp[col + 1];
if (chars[col] == '1') {
dp[col + 1] = Math.min(Math.min(dp[col], dp[col + 1]), northwest) + 1;
maxSide = Math.max(maxSide, dp[col + 1]);
} else dp[col + 1] = 0;
northwest = nextNorthwest;
}
}
return maxSide * maxSide;
}
}
这份代码的关键点就在于：
-
dp[col + 1]表示“上一行当前位置”的值，更新后会变成“当前行当前位置”的值 -
dp[col]表示“当前行左边”的值 -
northwest表示“上一行左上角”的值
也就是说，它用一个数组 + 一个额外变量，模拟出了二维 DP 所需要的三个状态。
一维 dp 中各变量的含义
1. dp[col + 1]
在更新之前，它表示：
上一行当前列的值，也就是“上边”
在更新之后，它就变成：
当前行当前列的值
2. dp[col]
由于我们是从左到右更新，所以 dp[col] 在当前循环中已经被更新过了，它表示：
当前行左边的值
3. northwest
这个变量用来保存更新前的 dp[col + 1] 的上一个位置，表示：
上一行左上角的值
这就是二维 DP 中的 dp[i - 1][j - 1]。
为什么要有 northwest
如果只用一维数组，随着 dp[col + 1] 被不断更新，原来“上一行左上角”的值就会丢失。
所以必须额外用一个变量提前保存它。
这也是很多同学第一次看空间优化版时最容易迷糊的地方。
代码解析
1. 边界判断
if (matrix == null || matrix.length < 1 || matrix[0].length < 1) return 0;
如果矩阵为空，直接返回 0。
2. 初始化基本变量
int height = matrix.length;
int width = matrix[0].length;
int maxSide = 0;
int[] dp = new int[width + 1];
-
height：矩阵行数 -
width：矩阵列数 -
maxSide：记录当前找到的最大正方形边长 -
dp：一维动态规划数组
这里 dp 的长度开成 width + 1，主要是为了方便处理边界，让转移写起来更统一。
3. 按行遍历矩阵
for (char[] chars : matrix) {
逐行处理矩阵。
每次进入新的一行时：
int northwest = 0;
表示当前行最开始时，左上角默认不存在，对应值为 0。
4. 按列遍历当前行
for (int col = 0; col < width; col++) {
逐列更新 DP。
5. 先保存旧的上方值
int nextNorthwest = dp[col + 1];
在更新 dp[col + 1] 之前，先把它保存起来。
因为它当前表示的是：
上一行当前列
而这个值在下一轮会成为“左上角”。
所以先存到 nextNorthwest 里，后面再赋给 northwest。
6. 如果当前位置是 '1'
if (chars[col] == '1') {
dp[col + 1] = Math.min(Math.min(dp[col], dp[col + 1]), northwest) + 1;
maxSide = Math.max(maxSide, dp[col + 1]);
}
这就是状态转移。
三个量分别对应：
-
dp[col]：左边 -
dp[col + 1]：上边 -
northwest：左上角
三者取最小值后再加 1，就是当前位置作为右下角时的最大正方形边长。
然后更新全局最大边长 maxSide。
7. 如果当前位置是 '0'
else dp[col + 1] = 0;
如果当前位置是 '0'，那它不可能成为全 1 正方形的右下角，所以边长只能是 0。
8. 更新 northwest
northwest = nextNorthwest;
为下一列做准备。
下一列需要的“左上角”，就是当前列更新前保存下来的“上一行当前列”。
9. 返回面积
return maxSide * maxSide;
题目要求返回面积，不是边长，所以最后要平方。
示例推演
我们看这个矩阵：
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
在逐步计算过程中：
-
某些位置只能形成边长为 1 的正方形
-
当遍历到第三行第四列、第五列附近时，左、上、左上都已经满足条件
-
于是能扩出一个边长为 2 的正方形
最终：
maxSide = 2
所以面积为：
2 * 2 = 4
为什么这题不能只看当前位置周围有多少个 1
有些同学第一次做这题时，可能会想到：
-
如果当前位置周围都是 1，是不是就能构成大正方形？
这种想法不够严谨。
因为正方形要求的是一个完整区域全部为 1，而不是只看边缘或者局部。
例如某个位置左边和上边看起来都不错，但左上角区域里藏着一个 0，那么这个更大的正方形其实就无效。
所以这题必须用 DP 来逐步维护“以当前位置为右下角时的最大正方形边长”。
复杂度分析
假设矩阵大小为 m × n。
时间复杂度
O(m × n)
因为每个位置只会被遍历一次。
空间复杂度
O(n)
只使用了一个长度为 n + 1 的一维数组和若干辅助变量。
如果用普通二维 DP，空间复杂度会是 O(m × n)。
和二维 DP 写法对比
二维 DP
优点：
-
更容易理解
-
状态含义更直观
缺点：
-
需要额外
O(m × n)空间
一维 DP 空间优化
优点：
-
空间复杂度降到
O(n) -
代码更高效
缺点：
-
northwest的含义不太直观 -
第一次看容易绕
所以如果是第一次学习，建议先理解二维 DP 的转移，再来看这份一维优化代码，就会顺很多。
总结
这道题最核心的思想就是：
以当前位置为右下角时，最大正方形边长取决于左、上、左上三个位置中最小的那个。
因为要扩成更大的正方形，这三个方向必须同时足够大。
所以状态转移公式是：
dp[i][j] = min(左, 上, 左上) + 1
而你这份代码又进一步做了空间优化，用一维数组加一个 northwest 变量，就把二维 DP 压缩掉了。
你可以把这题总结成一句话：
当前位置能扩出多大的正方形，取决于左、上、左上三个方向能撑多大。
