最大正方形

[编程题]最大正方形

热度指数：24736 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个由 '0' 和 '1' 组成的2维矩阵，返回该矩阵中最大的由 '1' 组成的正方形的面积。输入的矩阵是字符形式而非数字形式。

数据范围：矩阵的长宽满足 $0 \le n \le 20$ ,矩阵中的元素属于 {'1','0'}

进阶：空间复杂度 $O(n^2)$ ，时间复杂度 $O(n^2)$

示例1

输入

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

输出

示例2

输入

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

输出

算法知识视频讲解

查看答案及解析

推荐

我是一枚快乐的小菜鸡

二维动态规划，时间复杂度为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)

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)

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)

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)

Python 3

jjunun

class Solution:
    def solve(self , matrix ):
        row=len(matrix)
        col=len(matrix[0])
        dp=[[0 for _ in range(col+1)] for _ in range(row+1)]
        maxSide=0
        for i in range(1,row+1):
            for j in range(1,col+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
                    maxSide=max(maxSide,dp[i][j])
        return maxSide*maxSide

发表于 2021-07-17 11:41:18 回复(0)