美食网站需求分析,绝味鸭脖网站建设规划书,做网站界面,seo关键词优化的技巧在一个由 0 和 1 组成的二维矩阵内#xff0c;找到只包含 1 的最大正方形#xff0c;并返回其面积。 示例: 输入: 1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0输出: 4解法#xff1a;判断以某个点为正方形右下角时最大的正方形时#xff0c;那它的上方#xff0c;左方和左上…在一个由 0 和 1 组成的二维矩阵内找到只包含 1 的最大正方形并返回其面积。 示例: 输入: 1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0输出: 4解法判断以某个点为正方形右下角时最大的正方形时那它的上方左方和左上方三个点也一定是某个正方形的右下角否则该点为右下角的正方形最大就是它自己了。我们知道该点为右下角的正方形的最大边长最多比它的上方左方和左上方为右下角的正方形的边长多1最好的情况是是它的上方左方和左上方为右下角的正方形的大小都一样的这样加上该点就可以构成一个更大的正方形。但如果它的上方左方和左上方为右下角的正方形的大小不一样合起来就会缺了某个角落这时候只能取那三个正方形中最小的正方形的边长加1了。 class Solution {
public:int maximalSquare(vectorvectorchar matrix) {if(matrix.empty() || matrix[0].empty()) return 0;int nmatrix.size(),mmatrix[0].size();int ans0;int dp[n][m];memset(dp,0,sizeof(dp));for(int i0;in;i){if(matrix[i][0]1){dp[i][0]1;ans1;}}for(int i0;im;i){if(matrix[0][i]1){dp[0][i]1;ans1;}}for(int i1;in;i){for(int j1;jm;j){if(matrix[i][j]1)dp[i][j]min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))1;ansmax(ans,dp[i][j]);}}return ans*ans;}
}; 转载于:https://www.cnblogs.com/jkzr/p/10610105.html
