[数据结构与算法] 21. 最大正方形

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 21. 最大正方形 -> 正文阅读

[数据结构与算法]21. 最大正方形

221. 最大正方形https://leetcode.cn/problems/maximal-square/

难度中等1145

在一个由?'0'?和?'1'?组成的二维矩阵内，找到只包含?'1'?的最大正方形，并返回其面积。

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：

输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

输入：matrix = [["0"]]
输出：0

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j]?为?'0'?或?'1'

通过次数197,228提交次数403,355

方法一：动态规划

new一个二维数组存储在matrix[][]每个点上正方形的最大边长。

每个点只需要判断该点不是0，上方、右方、右斜上方的点不为0，此时可以构成一个正方形。若之前的三个点可以构成正方形，则选三个点中能构成的最小边长+1，为该点可以构成的最大正方形边长。

max记录出现的最大边长。

时间复杂度：两层循环：O(nm)

空间复杂度：辅助数组：O(nm)

class Solution {
    public int maximalSquare(char[][] matrix) {

        //动态推断

        int[][] ans = new int[matrix.length][matrix[0].length];
        int max = 0;

        for(int i=0;i<matrix.length;i++)
        {
            for(int j=0;j<matrix[0].length;j++)
            {
                //判断边界
                if(i==0 ||j==0) ans[i][j] = (int)matrix[i][j]-'0';
                else if(matrix[i-1][j-1]!='0' && (int)matrix[i-1][j]!='0' && (int)matrix[i][j-1]!='0'&& matrix[i][j]!='0')
                {
                    ans[i][j] = Math.min(Math.min(ans[i-1][j-1],ans[i-1][j]),ans[i][j-1])+1;
                    
                }
                else ans[i][j] = (int)matrix[i][j]-'0';
                if(ans[i][j]>max) max = ans[i][j];
            }
        }
        return max*max;
    }
}