题目描述:
在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4
思路:本题需要返回矩阵中最大的正方形面积,计算正方形面积只要知道边长即可。申请一个跟matrix矩阵维度相同的数组,将数组的第一行和第一列初始化成matrix的第一行和第一列。
状态转移方程:$dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1 $ , ,对应于matrix[i][j]的正方形的最右下角元素。
状态转移方程的得到方法:试想2*2的正方形,如果要保证正方形必须要除了左上左上角都是1才能构成。
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if(matrix.empty()||matrix[0].empty())
return 0;
int row=matrix.size();
int col=matrix[0].size();
vector<vector<int>> dp(row,vector<int>(col,0));
int maxsqsize=0;//对于这个变量的赋值需要注意
for(int i=0;i<row;i++){
dp[i][0]=matrix[i][0]-'0';
maxsqsize=max(maxsqsize,dp[i][0]);//只有一列的情况
}
for(int i=0;i<col;i++){
dp[0][i]=matrix[0][i]-'0';
maxsqsize=max(maxsqsize,dp[0][i]);//只有一行的情况
}
//此双层循环只有矩阵的行列维度>=2才会执行
for(int i=1;i<row;i++){
for(int j=1;j<col;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;
if(maxsqsize<dp[i][j])
maxsqsize=dp[i][j];
}
}
}
return pow(maxsqsize,2);
}
};
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAnYldHL0FWby9mZvwFN4ETMfdHLkVGepZ2XtxSZ6l2clJ3LcV2Zh1Wa9M3clN2byBXLzN3btgHL9s2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xCMy81dvRWYoNHLwEzX5xCMx8FesU2cfdGLwMzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsQTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5iMwYjM0EjYiFDMwMjY4AjNzYzXyUzN1ATMxAzLcFTMyIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLyM3Lc9CX6MHc0RHaiojIsJye.png)
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if(matrix.empty()||matrix[0].empty())
return 0;
int row=matrix.size();
int col=matrix[0].size();
vector<vector<int>> dp(row+1,vector<int>(col+1,0));
int maxsqsize=0;//多申请了一个单元,就不需要对这个元素做特别的处理了
//这个双层循环一定会执行
for(int i=1;i<=row;i++){
for(int j=1;j<=col;j++){
if(matrix[i-1][j-1]=='1'){
dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
if(maxsqsize<dp[i][j])
maxsqsize=dp[i][j];
}
}
}
return pow(maxsqsize,2);
}
};