题目描述
描述：给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。
返回一个数组 [r, c, size] ，其中 r, c 分别代表子方阵左上角的行号和列号，size 是子方阵的边长。若有多个满足条件的子方阵，返回 r 最小的，若 r 相同，返回 c 最小的子方阵。若无满足条件的子方阵，返回空数组。
示例 1:
输入:
[
[1,0,1],
[0,0,1],
[0,0,1]
]
输出: [1,0,2]
解释: 输入中 0 代表黑色，1 代表白色，标粗的元素即为满足条件的最大子方阵
示例 2:
输入:
[
[0,1,1],
[1,0,1],
[1,1,0]
]
输出: [0,0,1]
提示：
matrix.length == matrix[0].length <= 200
解题思路
思路：最直观的想法是，穷举。依次遍历从矩阵中某一点开始出发的最大子矩阵，在遍历某一点时，先判断其向右方向的最大值，然后再从该最大值逐渐减小去判断以该点为左上角的子矩阵是否四边均是黑边，同步更新最大值即可。（超时36/37）
class Solution {
public:
//从(i,j)出发右边长度为size的
bool check(vector<vector<int>>& matrix,int i,int j,int size,int m,int n)
{
//某一边不够长度
if(i+size-1>=m||j+size-1>=n)
return false;
//左边
for(int k=i;k<i+size;k++)
{
if(matrix[k][j]!=0)
return false;
}
//下边
for(int k=j;k<j+size;k++)
{
if(matrix[i+size-1][k]!=0)
return false;
}
//右边
for(int k=i;k<i+size;k++)
{
if(matrix[k][j+size-1]!=0)
return false;
}
return true;
}
vector<int> findSquare(vector<vector<int>>& matrix) {
int m=matrix.size();
if(m==0)
return vector<int>();
int n=matrix[0].size();
vector<int> res(3,-1);
//从左向右从上向下遍历矩阵
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
//假设当前为黑色则只向一个方向遍历找到黑色最大边
if(matrix[i][j]==0)
{
//标记一下当前位置开始右边最大的边
int size=0;
//cout<<i<<" "<<j<<" "<<size<<endl;
//从(i,j)向右找到黑色最大长度
for(int k=j;k<n;k++)
{
if(matrix[i][k]==0)
size++;
else
break;
}
//cout<<i<<" "<<j<<" "<<size<<endl;
bool flag=false;
//判断四边是否满足
while(size>=1)
{
if(check(matrix,i,j,size,m,n)&&size>res[2])
{
flag=true;
res[0]=i;
res[1]=j;
res[2]=size;
break;
}
//从最大到最小
size--;
}
}
}
}
//判断
return res[0]==-1?vector<int> ():res;
}
};
优化：动态规划。dp[r][c][0/1]分别表示以坐标(r,c)为起点向右/下最多的连续黑色块数量。由于是向右/向下，故从下向上遍历从右向左遍历，即逆向更新即可，其中根据行来更新向下，根据列来更新向右。注意，以坐标(r,c)为左上角的子矩阵边长为向右和向下最多的连续黑色块数量两者中的最小值，此时还需要满足(r+len-1,c)向右和(r,c+len-1)向下最多的连续黑色块数量大于等于len才行！！！文章来源：https://www.toymoban.com/news/detail-519127.html
class Solution {
public:
vector<int> findSquare(vector<vector<int>>& matrix) {
vector<int> res(3,0);
int n=matrix.size();
if(n==0)
return {};
if(n==1)
{
if(matrix[0][0]==0)
return {0,0,1};
else
return {};
}
//dp[r][c][0/1]代表以坐标(r,c)为起点向右/下最多的连续黑色块数量
vector<vector<vector<int>>> dp(n,vector<vector<int>>(n,vector<int>(2)));
//逆向遍历
for(int r=n-1;r>=0;r--)
{
for(int c=n-1;c>=0;c--)
{
//当前为1则连续黑色均为0
if(matrix[r][c]==1)
{
dp[r][c][0]=0;
dp[r][c][1]=0;
}
else
{
//根据r统计下方
if(r<n-1)
dp[r][c][1]=dp[r+1][c][1]+1;
else
dp[r][c][1]=1;
//根据c统计右方
if(c<n-1)
dp[r][c][0]=dp[r][c+1][0]+1;
else
dp[r][c][0]=1;
//更新当前最大子方针
int len=min(dp[r][c][0],dp[r][c][1]);
while(len>=res[2])
{
//当前右边和下边 也要保证下边右方和右边下方
if(dp[r+len-1][c][0]>=len&&dp[r][c+len-1][1]>=len)
{
res={r,c,len};
break;
}
len--;
}
}
}
}
return res;
}
};
总结：超时，则说明需要优化时间复杂度，再来看，存在重复子问题，即黑色块数量是连续的，故此时就涉及到递推公式，这不就想到了动态规划！文章来源地址https://www.toymoban.com/news/detail-519127.html
到了这里，关于【程序员面试金典】面试题 17.23. 最大黑方阵的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
