最大正方形

[编程题]最大正方形

热度指数：25022 时间限制：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)

Python3

在写日记的大师兄很洒脱

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最大正方形
# @param matrix char字符型二维数组 
# @return int整型
#
class Solution:
    def solve(self , matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
        m, n = len(matrix), len(matrix[0])
        f = [[0]*(n+1) for _ in range(m+1)]
        res = 0
        for i in range(1,m+1):
            for j in range(1,n+1):
                if matrix[i-1][j-1]=='1':
                    f[i][j] = min(f[i-1][j-1], f[i-1][j], f[i][j-1])+1
                    res = max(res, f[i][j])
        return res*res

发表于 2025-05-23 10:50:56 回复(0)