首页 > 试题广场 >

最大正方形

[编程题]最大正方形
  • 热度指数：24749 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个由 '0' 和 '1' 组成的2维矩阵，返回该矩阵中最大的由 '1' 组成的正方形的面积。输入的矩阵是字符形式而非数字形式。

数据范围：矩阵的长宽满足 ,矩阵中的元素属于 {'1','0'}
进阶：空间复杂度 ， 时间复杂度
示例1

输入

[[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]

输出

4
示例2

输入

[[1,0,0],[0,0,0],[0,0,0]]

输出

1
算法知识视频讲解
添加回答
推荐
我是一枚快乐的小菜鸡头像 我是一枚快乐的小菜鸡
二维动态规划，时间复杂度为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号头像 牛客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头像 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头像 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)
唐氏综合征头像 唐氏综合征
 使用 dp 做的话，需要找到以 i, j 为有效正方形的右下角坐标的最大正方形的边长：
① 初始化第一行和第一列，找到 dp[i][0] 和 dp[0][j] 为1 的坐标，最大正方形就是为1
② 填充 dp 数组：
    在填充 dp[i][j] 时, 如果dp[i][j] == 0 则无法构成正方形，因此要找到以 i, j 为正方形的右下角坐标时，需要满足 dp[i][j] == 1, 由于求解的是正方形的边长而不是矩形的边长，因此，要找到 dp[i-1][j] ,dp[i][j-1], dp[i-1][j-1] 中的最小值，因为这三个值但凡有一个是0，则就可以认为当前点无法构成 > 1 的正方形，想要构成 > 1 的正方形，就必须保证这三个值都大于0，说明都是有效的正方形，又由于当前的格子值也为 '1'， 因此肯定能构成更大的正方形，因此要 + 1， 如下是代码实现：

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最大正方形
     * @param matrix char字符型二维数组
     * @return int整型
     */
    public int solve (char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] dp = new int[rows][cols];
        int maxSide = 0;

        // 初始化第一行和第一列
        for (int i = 0; i < rows; i++) {
            if(matrix[i][0] == '1')
                dp[i][0] = 1;
            
        }
        for (int j = 0; j < cols; j++) {
            if(matrix[0][j] == '1')
                dp[0][j] = 1;
        }

        // 动态规划填充dp数组
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }

        return maxSide * maxSide;
    }
}



发表于 2024-06-26 16:19:53 回复(0)
Python 3
liangzhengjie头像 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头像 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头像 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号头像 牛客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头像 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头像 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号头像 牛客977980134号
使用动态规划
发表于 2021-09-19 18:21:10 回复(0)
C++
Reanz头像 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头像 小熊_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)
提交观点

问题信息

动态规划
上传者：牛客332641号
难度：
57条回答 4997浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最大正方形

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号