LeetCode 221. 最大正方形
题目核心
给定一个由字符 '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"]
]其中最大正方形的边长是 2，面积是：
2 * 2 = 4解题思考过程
第一步：理解问题
在二维矩阵中找最大的全1正方形。正方形的特点是四条边等长。
第二步：暴力解法
最直接的思路：遍历每个格子，如果是1，就以它为左上角，尝试扩展正方形的边长。
for i from 0 to rows-1:
for j from 0 to cols-1:
if matrix[i][j] == '1':
max_len = 1
while 可以扩展:
检查右下方的格子是否全是1
max_len++检查扩展时需要遍历新的一行和一列，时间复杂度很高：
时间复杂度：O(m*n*min(m,n)^2)
空间复杂度：O(1)第三步：想到动态规划
能不能用动态规划？定义 dp[i][j] 表示以 (i,j) 为右下角的最大正方形边长。
观察规律：
如果 matrix[i][j] == '1':
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
为什么？
- dp[i-1][j]：上方正方形的边长
- dp[i][j-1]：左方正方形的边长
- dp[i-1][j-1]：左上方正方形的边长
- 取最小值 + 1，因为正方形的边长受限于最短的那个方向示例：
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
dp[1][2] = min(dp[0][2], dp[1][1], dp[0][1]) + 1 = min(1,0,0) + 1 = 1
dp[2][3] = min(dp[1][3], dp[2][2], dp[1][2]) + 1 = min(1,1,1) + 1 = 2第四步：空间优化
观察动态规划的公式，每次只需要 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]，可以用一维数组优化：
用 prev 保存 dp[i-1][j-1]
用 curr[j] 保存当前行的值
遍历过程：
temp = curr[j]
curr[j] = min(curr[j], curr[j-1], prev) + 1
prev = temp空间复杂度从 O(m*n) 降到 O(n)！
第五步：边界条件
- 第一行和第一列：如果是1，dp值就是1
- 如果矩阵为空：返回0
- 如果全是0：返回0
第六步：最终代码
时间复杂度：O(m*n)
空间复杂度：O(n) 或 O(m*n)这是最优解法！
解法一：二维前缀和 + 枚举正方形
当前代码使用的是二维前缀和。
核心思路是：先用前缀和快速计算任意矩形区域中有多少个 1，再枚举每一个可能的正方形。如果一个边长为 side 的正方形中 1 的数量等于 side * side，说明这个正方形全部由 1 组成。
var maximalSquare = function (matrix) {
const m = matrix.length;
const n = matrix[0].length;
const pre = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
pre[i][j] =
Number(matrix[i - 1][j - 1]) +
pre[i - 1][j] +
pre[i][j - 1] -
pre[i - 1][j - 1];
}
}
let maxSide = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
for (let side = maxSide + 1; i + side <= m && j + side <= n; side++) {
const sum =
pre[i + side][j + side] -
pre[i][j + side] -
pre[i + side][j] +
pre[i][j];
if (sum === side * side) {
maxSide = side;
} else {
break;
}
}
}
}
return maxSide * maxSide;
};二维前缀和复习
二维前缀和可以理解成：提前记录从左上角到当前位置这一整块区域的数字和。
这里定义：
pre[i][j] 表示 matrix 中：
第 0 行到第 i - 1 行
第 0 列到第 j - 1 列
这个矩形区域内所有数字的和因为 matrix 里存的是字符 '0' 和 '1'，所以构造前缀和时要用：
Number(matrix[i - 1][j - 1]);把字符转成数字。
为什么 pre 要多开一行一列
代码中创建的是：
const pre = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));也就是 pre 的行数和列数都比原矩阵多 1。
这样做的好处是处理边界更简单。比如第一行、第一列不需要额外判断越界，因为：
pre[0][j] = 0
pre[i][0] = 0它们相当于一圈空白边界。
所以 pre[i][j] 对应的原矩阵位置是：
matrix[i - 1][j - 1]前缀和构造公式
当前格子的前缀和来自四部分：
pre[i][j] =
Number(matrix[i - 1][j - 1]) +
pre[i - 1][j] +
pre[i][j - 1] -
pre[i - 1][j - 1];可以这样理解：
pre[i - 1][j]是当前格子上方整块区域的和。pre[i][j - 1]是当前格子左边整块区域的和。pre[i - 1][j - 1]被上面两块区域重复计算了一次，所以要减掉。- 最后加上当前格子自己的值。
对应关系是：
上方区域 + 左方区域 - 左上重复区域 + 当前格子如何查询一个正方形的和
假设正方形的左上角是 (i, j)，边长是 side。
它覆盖的区域是：
行：i 到 i + side - 1
列：j 到 j + side - 1使用二维前缀和后，可以用 O(1) 时间得到这个正方形里所有元素的和：
const sum =
pre[i + side][j + side] - pre[i][j + side] - pre[i + side][j] + pre[i][j];这个公式对应的是：
目标区域 =
右下大矩形
- 上方多出来的区域
- 左边多出来的区域
+ 左上角被重复减掉的区域如果：
sum === side * side;说明这个正方形里面的 1 的数量等于它的总格子数，所以它一定全部是 1。
为什么可以从 maxSide + 1 开始枚举
当前已经找到的最大边长是 maxSide。
如果继续尝试边长小于或等于 maxSide 的正方形，就算成功，也不能更新答案。
所以从：
let side = maxSide + 1;开始尝试即可。
这样做可以减少一些没有必要的判断。
为什么遇到失败可以 break
对于固定的左上角 (i, j)，如果边长为 side 的正方形已经不是全 1，说明这个正方形里面至少有一个 0。
那么以同一个左上角继续扩大成更大的正方形时，这个 0 仍然会被包含在里面。
所以更大的正方形也不可能是全 1，可以直接：
break;跳出当前左上角的边长枚举。
复杂度
- 时间复杂度：
O(m * n * min(m, n)) - 空间复杂度：
O(m * n)
其中 m 是矩阵行数，n 是矩阵列数。
二维前缀和的构造需要 O(m * n)。之后枚举每个左上角，并尝试不同边长，每次判断正方形是否合法都是 O(1)。
解法二：动态规划
这道题更常见的最优写法是动态规划。
定义：
dp[i][j] 表示以 matrix[i - 1][j - 1] 作为右下角的最大正方形边长如果当前位置是 '0'，那么它不能作为全 1 正方形的右下角：
dp[i][j] = 0如果当前位置是 '1'，它能组成的最大正方形取决于三个方向：
上方：dp[i - 1][j]
左方：dp[i][j - 1]
左上：dp[i - 1][j - 1]三者中最短的那一边，决定了当前位置最多能扩展多大的正方形：
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;完整代码：
var maximalSquare = function (matrix) {
const m = matrix.length;
const n = matrix[0].length;
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
let maxSide = 0;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (matrix[i - 1][j - 1] === "1") {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
maxSide = Math.max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
};为什么动态规划要看三个方向
当前位置如果要作为一个边长更大的正方形右下角，那么它的：
- 上方必须能提供足够高度。
- 左方必须能提供足够宽度。
- 左上必须本身已经形成一个正方形。
只要这三个方向中有一个比较短，当前正方形就无法继续扩大。
所以要取三者最小值，再加上当前这个 '1'：
当前最大边长 = min(上方, 左方, 左上) + 1两种解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 二维前缀和 + 枚举 | O(m * n * min(m, n)) | O(m * n) | 思路直观，可以快速判断某个区域是否全是 1 |
| 动态规划 | O(m * n) | O(m * n) | 本题最常用解法，效率更高 |
面试中优先写动态规划；如果是为了复习二维前缀和，你现在这个写法也很适合练习“区域和查询”的思想。