最大正方形_

推荐

我是一枚快乐的小菜鸡

二维动态规划，时间复杂度为O(m*n)。
用dp[i][j]表示以matrix[i][j]为右下角的全为1组成的最大正方形的边长，则:
1. 若matrix[i][j] == 0, 则dp[i][j] = 0
2. 若matrix[i][j] == 1, 则dp[i][j] = min{dp[i-1][j], dp[i][j-1], dp[i-1][j-1]} + 1

原因可以看下面这张图:

class Solution {
public:
    /**
     * 最大正方形
     * @param matrix char字符型vector<vector<>> 
     * @return int整型
     */
    int solve(vector<vector<char> >& matrix) {
        if(matrix.size()==0 || matrix[0].size()==0) {
            return 0;
        }
        int Rows = matrix.size(), Cols = matrix[0].size();
        vector<vector<int>> dp(Rows, vector<int>(Cols, 0));
        int maxSide = 0;
        for(int i = 0; i < Rows; i++) {
            for(int j = 0; j < Cols; j++) {
                if(matrix[i][j] == '1') {
                    if(i==0 || j==0) {
                        dp[i][j] = 1;
                    }
                    else {
                        dp[i][j] = std::min(std::min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                    }
                }
                maxSide = std::max(maxSide, dp[i][j]);
            }
        }
        return (long long)maxSide * maxSide;
    }
};

编辑于 2021-07-06 10:53:46 回复(1)

惠灵顿靖

import java.util.*;
//https://www.nowcoder.com/practice/0058c4092cec44c2975e38223f10470e?tpId=117&&tqId=37832&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking

public class Solution {
    /**
     * 最大正方形
     * @param matrix char字符型二维数组 
     * @return int整型
     */
 public int solve (char[][] matrix) {
    //二维矩阵的宽和高
    int height = matrix.length;
    int width = matrix[0].length;
    int[][] dp = new int[height + 1][width + 1];
    int maxSide = 0;//最大正方形的宽
    for (int i = 1; i <= height; i++) {
        for (int j = 1; j <= width; j++) {
            if (matrix[i - 1][j - 1] == '1') {
                //递推公式
                dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1])) + 1;
                //记录最大的边长
                maxSide = Math.max(maxSide, dp[i][j]);
            }
        }
    }
    //返回正方形的面积
    return maxSide * maxSide;
}
}

发表于 2021-07-15 22:47:37 回复(0)

Java

牛客577127890号

import java.util.*;


public class Solution {
    /**
     * 最大正方形
     * @param matrix char字符型二维数组 
     * @return int整型
     */
    public int solve (char[][] matrix) {
        // write code here
        int [][]dp = new int[matrix.length][matrix[0].length];
        int bc = 0;
        dp[0][0]=0;
        for(int i=0;i<dp.length;i++){
            dp[i][0]=matrix[i][0]-'0';
        }
        for(int j=0;j<dp[0].length;j++){
            dp[0][j]=matrix[0][j]-'0';
        }
        for(int i=1;i<dp.length;i++){
            for(int j=1;j<dp[0].length;j++){
                if(matrix[i][j]=='0'){
                    dp[i][j]=0;
                }else{
                    int up = dp[i-1][j];
                    int left = dp[i][j-1];
                    int ul = dp[i-1][j-1];
                    if(up==left && up==ul){
                        dp[i][j]=up+1;
                    }else{
                        int m = Math.min(up,Math.min(left,ul));
                        dp[i][j]=m+1;
                    }
                }
            }
        }
        for(int i=0;i<dp.length;i++){
            for(int j=0;j<dp[0].length;j++){
                bc = Math.max(bc,dp[i][j]);
            }
        }
        int area = bc*bc;
        return area;
    }
}

前排提示：这道题有个很坑的地方，java输入的matrix是字符型。自测的时候算出来面积两千多，一直不知道啥问题，一看函数参数列表......

发表于 2020-08-25 17:10:52 回复(0)

C/C++

BrainerGao

/**
 * 最大正方形
 * @param matrix char字符型二维数组 
 * @param matrixRowLen int matrix数组行数
 * @param matrixColLen int* matrix数组列数
 * @return int整型
 */
int min(int a, int b)
{
    return a < b ? a : b;
}
int max(int a, int b)
{
    return a > b ? a : b;
}
int solve(char** matrix, int matrixRowLen, int* matrixColLen ) {
    if (matrixRowLen == 0 || matrixColLen == 0) {
        return 0;
    }
    int res = 0;
    for (int i = 0; i < matrixRowLen; i++) {
        for (int j = 0; j < *matrixColLen; j++) {
            if (matrix[i][j] == '1' && i > 0 && j > 0) {
                matrix[i][j] = 1 + min(min(matrix[i-1][j-1], matrix[i-1][j]), matrix[i][j-1]);
                res = max(res, (matrix[i][j] - '0'));
            }
        }
    }
    return res * res;
}

发表于 2021-02-28 18:51:24 回复(0)

一寸松糕

import java.util.*;

public class Solution {
/**
* 最大正方形
* @param matrix char字符型二维数组
* @return int整型
*/
public static boolean checkAllOne(int row,int col,int side,char[][]mat){
for(int i=row;i<row+side;i++){
for(int j=col;j<col+side;j++){
if(mat[i][j]=='0')
return false;
}
}
return true;
}
public int solve (char[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
int maxArea=0;
for(int i=0;i<rows-1;i++){
for(int j=0;j<cols-1;j++){
int maxSide = Math.min(rows-i,cols-j);
for(int k=1;k<=maxSide;k++){
if(checkAllOne(i,j,k,matrix))
maxArea = Math.max(maxArea,k*k);
}
}
}
return maxArea;
}
}

发表于 2020-09-03 11:07:15 回复(0)

Stackingrule

暴力法---把数组中每一个点都当成正方形的左顶点来向右下方扫描，来寻找最大正方形

    int getSquareArea(vector<int> &v, int k) {
        if (v.size() < k) return 0;
        int count = 0;
        for (int i = 0; i < v.size(); ++i) {
            if (v[i] != k) count = 0; 
            else ++count;
            if (count == k) return k * k;
        }
        return 0;
    }

发表于 2020-08-13 16:15:25 回复(0)

Python 3

liangzhengjie

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最大正方形
# @param matrix char字符型二维数组 
# @return int整型
#
class Solution:
    def solve(self , matrix: List[List[str]]) -> int:
        # write code here
        if len(matrix) == 0:
            return 0
        if len(matrix[0]) == 0:
            return 0
        res = 0

        dp = [[0 for i in range(len(matrix[0]))] for j in range(len(matrix))]

        for i in range(len(matrix[0])):
            if matrix[0][i] == '1':
                dp[0][i] = 1
        
        for j in range(len(matrix)):
            if matrix[j][0] == '1':
                dp[j][0] = 1

        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == '1':
                    dp[i][j] = 1

                    min_len = min(dp[i-1][j], dp[i][j-1])
                    if matrix[i-min_len][j-min_len] == '1':
                        dp[i][j] += min_len
                    else:
                        dp[i][j] += min_len-1


        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                res = max(res,  dp[i][j])

        return res*res

编辑于 2024-04-05 17:52:05 回复(0)

强大的茶叶蛋不放弃

import java.util.*;

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

* 最大正方形

* @param matrix char字符型二维数组

* @return int整型

*/

public int solve (char[][] matrix) {

int result = 0;

if (matrix.length != 0) {

int width = matrix[0].length; //列

int height = matrix.length; //行

int [][] dp = new int[height + 1][width + 1];

for (int i = 1; i <= height; i++) {

for (int j = 1; j <= width; j++) {

if (matrix[i - 1][j - 1] == '1') {

dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i - 1][j - 1]), dp[i][j - 1]) + 1;

result = Math.max(result, dp[i][j]);

}

return result * result;

}

发表于 2023-08-02 22:00:54 回复(0)

C++

Pierce_qiang

// 一眼以为是最大矩形。。反正基本一样思路
class Solution {
public:
    /**
     * 最大正方形
     * @param matrix char字符型vector<vector<>> 
     * @return int整型
     */
    int solve(vector<vector<char> >& matrix) {
        // write code here
        if(!matrix.size()||!matrix[0].size()) return 0;
        vector<vector<int>> dp(matrix.size(),vector<int>(matrix[0].size(),0));
        for(int i = 0;i<matrix.size();++i) dp[i][0] = matrix[i][0]=='1'? 1:0;
        for(int i = 0;i<matrix.size();++i){
            for(int j = 1;j<matrix[0].size();++j){
                if(matrix[i][j]=='1') dp[i][j] = dp[i][j-1]+1;
            }
        }
        int res = 1;
        for(int i = 0;i<matrix.size();++i){
            for(int j = 0;j<matrix[0].size();++j){
                if(dp[i][j]>0){
                    int dx = dp[i][j];int dy=  1;
                    int x,y; x = j, y= i-1;
                    while(y>=0&&dp[y][x]>0){
                        dy++;
                        dx = min(dx,dp[y][x]);
                                                //确定是不是正方形
                        if(dx==dy) res = max(res, dx*dy);
                        y--;
                    }
                }
            }
        }
        return res;
    }
};

发表于 2022-04-15 11:09:18 回复(0)

C++

勇敢牛牛，不怕困难！

class Solution {
public:
  int solve(vector<vector<char> >& matrix) {
    // corner case
    if (matrix.empty()) return 0;
    
    const size_t m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    
    int ans = 0;
    for (int y = 1; y <= m; ++y)
      for (int x = 1; x <= n; ++x)
        if (matrix[y - 1][x - 1] == '1') {
          // 核心：状态转移方程
          dp[y][x] = 1 + min({dp[y - 1][x], dp[y][x - 1], dp[y - 1][x - 1]});
          ans = max(ans, dp[y][x]);
        }
    
    return ans * ans;
  }
};

发表于 2022-01-31 19:00:11 回复(0)

Python 3

Joy_9

class Solution:
    def solve(self , matrix: List[List[str]]) -> int:
        # write code here
        if not matrix:
            return 0
        n=len(matrix[0])
        m=len(matrix)
        max_len=0
        dp=[[0]*(n+1) for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                if matrix[i-1][j-1]=='1':
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
                    max_len=max(max_len,dp[i][j])
        return max_len*max_len

发表于 2022-01-22 05:34:40 回复(0)

进击的喵哥

import java.util.*;

public class Solution {
    /**
     * 最大正方形
     * @param matrix char字符型二维数组 
     * @return int整型
     */
    public int solve (char
[][] matrix) {
        // write code here
        int 
[][]dp = new int
[matrix.length][matrix[0].length];
        int bc = 0;
        dp
[0][0]=0;
        for(int i=0;i<dp.length;i++){
            dp
[i][0]=matrix
[i][0]-'0';
        }
        for(int j=0;j<dp
[0].length;j++){
            dp
[0][j]=matrix
[0][j]-'0';
        }
        for(int i=1;i<dp.length;i++){
            for(int j=1;j<dp
[0].length;j++){
                if(matrix
[i][j]=='0'){
                    dp
[i][j]=0;
                }else{
                    int up = dp
[i-1][j];
                    int left = dp
[i][j-1];
                    int ul = dp
[i-1][j-1];
                    if(up==left && up==ul){
                        dp
[i][j]=up+1;
                    }else{
                        int m = Math.min(up,Math.min(left,ul));
                        dp
[i][j]=m+1;
                    }
                }
            }
        }
        for(int i=0;i<dp.length;i++){
            for(int j=0;j<dp
[0].length;j++){
                bc = Math.max(bc,dp
[i][j]);
            }
        }
        int area = bc*bc;
        return area;
    }
}

发表于 2022-01-19 08:58:52 回复(0)

C++

牛客831599296号

class Solution {
public:
/**
* 最大正方形
* @param matrix char字符型vector<vector<>>
* @return int整型
*/
int solve(vector<vector<char> >& matrix) {
// write code here
if(matrix.size() == 0)
return 0;
int max = 0;
vector<vector<int>> dp(matrix.size(), vector<int>(matrix[0].size(), 0));
for(int i=0;i<matrix.size();i++)
{
for(int j=0;j<matrix[0].size();j++)
{
if(matrix[i][j] == '1')
dp[i][j] = 1;
else{
continue;
}
if(i-1 >=0 && j-1 >= 0)
dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1;
if(dp[i][j] > max)
max = dp[i][j];
}
}
return max * max;
}
};

发表于 2021-11-21 13:22:18 回复(0)

LDew

import java.util.*;


public class Solution {
    public int solve (char[][] grap) {
        int n = grap.length;
        if(n == 0)return 0;
        int m = grap[0].length;
        int f[][] = new int[n + 3][m + 3];
        int len = 0;
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
                if(grap[i - 1][j - 1] == '1'){
                    f[i][j] = Math.min(f[i - 1][j - 1],Math.min(f[i - 1][j],f[i][j - 1])) + 1;
                    len = Math.max(len,f[i][j]);
                }
            }
        }
        return len * len;
    }
}

发表于 2021-11-19 09:45:21 回复(0)

C++

不经历怎么能成长

class Solution {
public:
    /**
     dp[i][j]:以第i行j列为最右下角元素 前i行j列的最大边长
     当第i行j列元素为1时，dp[i][j]=min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1]))+ 1;
     当第i行j列元素为0时,dp[i][j]=0;
     */
    int solve(vector<vector<char> >& matrix) {
        int height = matrix.size();
        if(!height) return 0;
        int width = matrix[0].size();
        vector<vector<int> > dp(height+1,vector<int>(width+1, 0));
        int maxSide = 0;//最大正方形的宽
        for (int i = 1; i <= height; i++) {
            for (int j = 1; j <= width; j++) {
            if (matrix[i - 1][j - 1] == '1') {
                //递推公式
                dp[i][j] = min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i][j - 1]))+ 1;
                maxSide = max(maxSide, dp[i][j]);
            }
            }
        }
        //返回正方形的面积
        return maxSide * maxSide;
    }
};

发表于 2021-11-18 10:40:55 回复(0)

Java

QinGL_ZYW

单调栈

public int solve (char[][] matrix) {
    if(matrix == null || matrix.length == 0) return 0;
    Stack<Integer> stack = new Stack<>();
    int maxRes = 0;
    int m = matrix.length, n = matrix[0].length;
    int[] arr = new int[n+2];
 
    for(int i = 0; i < m; i++){
        stack.push(0);
        for(int j = 1; j < n+2; j++){
            if(j < n+1){
                if(matrix[i][j-1] == '1'){
                    arr[j]++;
                }else{
                    arr[j] = 0;
                }
            }
            while(!stack.isEmpty() && arr[stack.peek()] > arr[j]){
                int length = Math.min(arr[stack.pop()], j-stack.peek()-1);
                maxRes = Math.max(maxRes, length);
            }
            stack.push(j);
        }
        while(!stack.isEmpty()) stack.pop();
    }
    return maxRes*maxRes;
}

动态规划

public int solve (char[][] matrix) {
    if(matrix == null || matrix.length == 0) return 0;
    int m = matrix.length, n = matrix[0].length;
    int[][] dp = new int[m+1][n+1];
    int max = 0;
    for(int i = 1; i < m+1; i++){
        for(int j = 1; j < n+1; j++){
            if(matrix[i-1][j-1] == '1'){
                dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
                max = Math.max(max, dp[i][j]);
            }
        }
    }
    return max*max;
}

发表于 2021-10-16 16:12:30 回复(0)

Java

牛客977980134号

使用动态规划

发表于 2021-09-19 18:21:10 回复(0)

C++

Reanz

class Solution {
public:
    int solve(vector<vector<char> >& matrix) {
        // write code here
        int maxSide=0;
        int m=matrix.size(),n=matrix[0].size();
        vector<vector<int>> dp(m,vector<int>(n));
        //动态规划
        //数组含义:dp[i][j]表示当前最大边长
        //递推公式:正方形,当遍历到一个1时,需要判断左上,上,左是否都为1.都为1则加1,不为1则不变由于是01矩阵,只需要利用min函数即可
        //初始化:dp数组边长应该都为0,不需要特别初始化
        //遍历顺序,根据递推公式,从上到下,从左到右即可
        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;//特殊情况,没有左上,上,左.默认边长为1的正方形
                    else dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
                }
                maxSide=max(maxSide,dp[i][j]);//每次计算完需要比较存储
            }
        }
        return maxSide*maxSide;
    }
};

发表于 2021-09-16 14:03:13 回复(0)

Python 3

可恶，被他装到了

class Solution:
def solve(self , matrix ):
result = 0
for i in range(len(matrix)):
for j in range(len(matrix[0])):
n = 1
while self.issquare(matrix, i, j, n):
n += 1
if n-1 > result:
result = n-1
return result*result

def issquare(self, matrix, i, j, n):
if n == 1:
if matrix[i][j] == 1:
return 1
else:
return 0
if i + n -1 < len(matrix) and j + n -1 < len(matrix[0]):
for row in range(i,i+n-1):
if not matrix[row][j+n-1]:
return 0
for col in range(j,j+n):
if not matrix[i+n-1][col]:
return 0
return 1
else:
return 0

发表于 2021-08-28 21:40:05 回复(0)

C++

小熊_008

动态规划：

dp 数组含义： dp[i][j]: 以 matrix[i - 1][j - 1] 为右下角的最大正方形边长。

class Solution {
public:
    /**
     * 最大正方形
     * @param matrix char字符型vector<vector<>> 
     * @return int整型
     */
    int solve(vector<vector<char> >& matrix) {
        // write code here
        int row = matrix.size();
        int col = matrix[0].size();
        int maxSize = 0;
        
        // dp[i][j]: 以 matrix[i - 1][j - 1] 为右下角的最大正方形边长。
        vector<vector<int>> dp(row + 1, vector<int>(col + 1, 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(
                                    dp[i][j - 1],
                                    min(dp[i - 1][j - 1], dp[i - 1][j]) 
                                  ) + 1;
                    maxSize = maxSize < dp[i][j] ? dp[i][j] : maxSize;
                }
                else {
                    dp[i][j] = 0;
                }
            }
        }
        
        return maxSize * maxSize;
    }
};

发表于 2021-08-22 15:24:35 回复(0)

C++

开车的阿Q

class Solution {
public:
    int solve(vector<vector<char> >& matrix) {
        int ans=0;//返回答案
        int l=matrix.size() ,w=matrix[0].size();//矩阵长宽
        for (int i=1;i<l;i++) 
        {
            for (int j=1;j<=w;j++) 
            {
                if(matrix[i][j]=='1')//符合递归条件
                {
                    //递推公式
                    matrix[i][j] = min(matrix[i - 1][j], min(matrix[i - 1][j - 1], matrix[i][j - 1])) + 1;
                    //记录最大的边长
                    ans = max(ans, (int)matrix[i][j]);
                }
            }
        }
        return (ans-'0')*(ans-'0');//转化为10进制输出
    }
};

原数组上硬搞

发表于 2021-08-17 00:23:12 回复(0)

最大正方形

输入

输出

输入

输出

暴力法---把数组中每一个点都当成正方形的左顶点来向右下方扫描，来寻找最大正方形

问题信息

热门推荐

通过挑战的用户

相关试题