在一个由0和1组成的二维矩阵内,找到只包含1的最大正方形,并返回其面积
时间: 2024-05-23 14:10:13 浏览: 108
这个问题可以使用动态规划来解决。我们可以创建一个相同大小的二维数组,用来记录每个位置为右下角的最大正方形的边长。如果当前位置为0,则最大正方形的边长显然是0;如果当前位置为1,则最大正方形的边长可以通过当前位置上、左、左上三个位置的最小值加1来更新。最终最大正方形的面积就是求出的最大边长的平方。
以下是代码实现:
int maximalSquare(vector<vector<char>>& matrix) {
int m = matrix.size();
if (m == 0) return 0;
int n = matrix[0].size();
int maxSide = 0;
vector<vector<int>> dp(m, vector<int>(n));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
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;
}
阅读全文