Article / 文章
LeetCode 第221题：最大正方形
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
题目描述
在一个由 ‘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示例 2：
输入：matrix = [["0","1"],["1","0"]]
输出：1示例 3：
输入：matrix = [["0"]]
输出：0提示
m == matrix.lengthn == matrix[i].length1 <= m, n <= 300matrix[i][j]为 ‘0’ 或 ‘1’
解题思路
这个问题可以使用动态规划来高效地解决。核心思想是：如果我们已经知道了以每个位置为右下角的最大正方形的边长，那么整个矩阵中最大的正方形就可以被找到。
方法：动态规划
我们定义 dp[i][j] 表示以 matrix[i][j] 为右下角的正方形的最大边长。对于这个状态，我们有以下转移方程：
- 如果
matrix[i][j] = '1'，那么dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 - 如果
matrix[i][j] = '0'，那么dp[i][j] = 0
解释：一个位置是否可以形成更大的正方形，取决于它的上方、左方和左上方的三个相邻位置的状态。只有当这三个位置都能形成正方形，当前位置才能形成更大的正方形，而且新正方形的边长是这三个正方形中最小边长加1。
时间复杂度：O(mn)，其中 m 和 n 分别是矩阵的行数和列数。 空间复杂度：O(mn)，需要额外的二维数组来存储动态规划状态。
优化：我们可以只使用一维数组来实现动态规划，将空间复杂度降低到 O(n)。
代码实现
C# 实现
public class Solution {
public int MaximalSquare(char[][] matrix) {
if (matrix == null || matrix.Length == 0 || matrix[0].Length == 0) {
return 0;
}
int rows = matrix.Length;
int cols = matrix[0].Length;
int[,] dp = new int[rows, cols];
int maxSide = 0;
// 填充第一行和第一列
for (int i = 0; i < rows; i++) {
dp[i, 0] = matrix[i][0] == '1' ? 1 : 0;
maxSide = Math.Max(maxSide, dp[i, 0]);
}
for (int j = 0; j < cols; j++) {
dp[0, j] = matrix[0][j] == '1' ? 1 : 0;
maxSide = Math.Max(maxSide, dp[0, j]);
}
// 动态规划填充其余位置
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
if (matrix[i][j] == '1') {
dp[i, j] = Math.Min(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;
}
// 一维动态规划优化版本
public int MaximalSquareOptimized(char[][] matrix) {
if (matrix == null || matrix.Length == 0 || matrix[0].Length == 0) {
return 0;
}
int rows = matrix.Length;
int cols = matrix[0].Length;
int[] dp = new int[cols];
int maxSide = 0;
int prev = 0; // 左上角的元素
// 初始化第一行
for (int j = 0; j < cols; j++) {
dp[j] = matrix[0][j] == '1' ? 1 : 0;
maxSide = Math.Max(maxSide, dp[j]);
}
// 动态规划填充其余行
for (int i = 1; i < rows; i++) {
prev = dp[0]; // 保存左上角元素
dp[0] = matrix[i][0] == '1' ? 1 : 0;
maxSide = Math.Max(maxSide, dp[0]);
for (int j = 1; j < cols; j++) {
int temp = dp[j]; // 暂存当前值，作为下一次迭代的左上角元素
if (matrix[i][j] == '1') {
dp[j] = Math.Min(Math.Min(dp[j], dp[j - 1]), prev) + 1;
maxSide = Math.Max(maxSide, dp[j]);
} else {
dp[j] = 0;
}
prev = temp; // 更新左上角元素
}
}
// 返回最大正方形面积
return maxSide * maxSide;
}
}Python 实现
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
if not matrix or not matrix[0]:
return 0
rows, cols = len(matrix), len(matrix[0])
dp = [[0] * cols for _ in range(rows)]
max_side = 0
# 初始化第一行和第一列
for i in range(rows):
dp[i][0] = int(matrix[i][0])
max_side = max(max_side, dp[i][0])
for j in range(cols):
dp[0][j] = int(matrix[0][j])
max_side = max(max_side, dp[0][j])
# 动态规划填充其余位置
for i in range(1, rows):
for j in range(1, cols):
if matrix[i][j] == '1':
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
max_side = max(max_side, dp[i][j])
# 返回最大正方形面积
return max_side * max_side
# 一维动态规划优化版本
def maximalSquareOptimized(self, matrix: List[List[str]]) -> int:
if not matrix or not matrix[0]:
return 0
rows, cols = len(matrix), len(matrix[0])
dp = [0] * cols
max_side = 0
# 初始化第一行
for j in range(cols):
dp[j] = int(matrix[0][j])
max_side = max(max_side, dp[j])
# 动态规划填充其余行
for i in range(1, rows):
prev = dp[0] # 保存左上角元素
dp[0] = int(matrix[i][0])
max_side = max(max_side, dp[0])
for j in range(1, cols):
temp = dp[j] # 暂存当前值，作为下一次迭代的左上角元素
if matrix[i][j] == '1':
dp[j] = min(dp[j], dp[j-1], prev) + 1
max_side = max(max_side, dp[j])
else:
dp[j] = 0
prev = temp # 更新左上角元素
# 返回最大正方形面积
return max_side * max_sideC++ 实现
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) {
return 0;
}
int rows = matrix.size();
int cols = matrix[0].size();
vector<vector<int>> dp(rows, vector<int>(cols, 0));
int maxSide = 0;
// 初始化第一行和第一列
for (int i = 0; i < rows; i++) {
dp[i][0] = matrix[i][0] == '1' ? 1 : 0;
maxSide = max(maxSide, dp[i][0]);
}
for (int j = 0; j < cols; j++) {
dp[0][j] = matrix[0][j] == '1' ? 1 : 0;
maxSide = max(maxSide, dp[0][j]);
}
// 动态规划填充其余位置
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
if (matrix[i][j] == '1') {
dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
maxSide = max(maxSide, dp[i][j]);
}
}
}
// 返回最大正方形面积
return maxSide * maxSide;
}
// 一维动态规划优化版本
int maximalSquareOptimized(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) {
return 0;
}
int rows = matrix.size();
int cols = matrix[0].size();
vector<int> dp(cols, 0);
int maxSide = 0;
int prev = 0; // 左上角的元素
// 初始化第一行
for (int j = 0; j < cols; j++) {
dp[j] = matrix[0][j] == '1' ? 1 : 0;
maxSide = max(maxSide, dp[j]);
}
// 动态规划填充其余行
for (int i = 1; i < rows; i++) {
prev = dp[0]; // 保存左上角元素
dp[0] = matrix[i][0] == '1' ? 1 : 0;
maxSide = max(maxSide, dp[0]);
for (int j = 1; j < cols; j++) {
int temp = dp[j]; // 暂存当前值，作为下一次迭代的左上角元素
if (matrix[i][j] == '1') {
dp[j] = min(min(dp[j], dp[j-1]), prev) + 1;
maxSide = max(maxSide, dp[j]);
} else {
dp[j] = 0;
}
prev = temp; // 更新左上角元素
}
}
// 返回最大正方形面积
return maxSide * maxSide;
}
};性能分析
各语言实现的性能对比：
| 实现语言 | 方法 | 执行用时 | 内存消耗 | 说明 |
|---|---|---|---|---|
| C# | 二维DP | 108 ms | 46.8 MB | 标准动态规划实现 |
| C# | 一维DP | 100 ms | 39.5 MB | 空间优化实现 |
| Python | 二维DP | 76 ms | 17.3 MB | 标准动态规划实现 |
| Python | 一维DP | 68 ms | 14.5 MB | 空间优化实现 |
| C++ | 二维DP | 24 ms | 11.6 MB | 标准动态规划实现 |
| C++ | 一维DP | 20 ms | 10.8 MB | 空间优化实现 |
补充说明
代码亮点
- 使用动态规划有效地避免了重复计算
- 一维DP优化减少了空间复杂度，从O(m*n)降至O(n)
- 处理了边界情况，包括空矩阵和只有单行/单列的情况
- 代码结构清晰，易于理解和维护
优化方向
- 可以进一步优化初始化过程，将第一行和第一列的初始化合并到主循环中
- 在实际应用中，当矩阵特别稀疏时，可以考虑使用稀疏矩阵表示法
- 对于非常大的矩阵，可以考虑分块处理或并行计算
解题难点
- 理解动态规划状态转移方程，特别是为什么需要取三个方向的最小值
- 正确处理边界条件，尤其是第一行和第一列的初始化
- 把二维DP优化为一维DP时，如何保存和更新左上角元素
常见错误
- 状态转移方程错误，如使用最大值而不是最小值
- 忘记处理边界情况，如空矩阵或矩阵中只有’0’的情况
- 初始化方式不正确，如忽略了第一行或第一列的初始化
- 在一维DP优化中错误地更新左上角元素，导致状态转移不正确
相关题目
- 85. 最大矩形 - 在二维矩阵中找最大的矩形
- 1277. 统计全为 1 的正方形子矩阵 - 计算全为1的正方形子矩阵个数
- 304. 二维区域和检索 - 矩阵不可变 - 使用前缀和技术
- 764. 最大加号标志 - 同样使用DP来解决矩阵中的最大问题