最大正方形
在一个由 '0' 和 '1' 组成的二维矩阵内,找到只包含 '1' 的最大正方形,并返回其面积。
分析:
#include<bits/stdc++.h>
#include<vector>
class Solution {
public:
int min33(int a,int b,int c){
int min3=a;
if(a>b) min3=b;
if(min3>c) min3=c;
return min3;
}
int max(int a,int b){
return a>b?a:b;
}
int maximalSquare(vector<vector<char>>& matrix) {
int rows = matrix.size(), columns = matrix[0].size();
vector<vector<int>> dp(rows, vector<int>(columns));
for(int i=0;i<rows;i++){
for(int j=0;j<columns;j++){
dp[i][j]=matrix[i][j]-'0'; //将matrix中char型转成int型
}
}
if(dp.size()==0) return 0; //如果dp中一个数都没有,return 0
for(int i=1;i<rows;i++){
for(int j=1;j<columns;j++){
if(dp[i][j]==1)
dp[i][j]=min33(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1;//更新dp
if(dp[i][j]==0) dp[i][j]=0;
}
}
int max1=0;
for(int i=0;i<rows;i++){ //找更新后dp中的最大值
for(int j=0;j<columns;j++){
max1=max(max1,dp[i][j]);
}
}
return max1*max1;
}
};