221. 最大正方形

题目描述

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

输入输出

1
2
3
4
5
6
7
8
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

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

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

基本思路

动态转移：转移思路求最大边长 边长平方即为面积 设dp[i][j]为以(i, j)为右下角且只包含1的正方形的边长最大值

有如下两种情况（边界）：
$$
\begin
{cases}
当在边界的时候（i或j为0）：dp[i][j] = 1 \\[3ex]
其他情况：dp[i][j]=\min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
\end
{cases}
$$
时间复杂度：$O(MN)$ 其中 M 和 M 是矩阵的行数和列数。需要遍历原始矩阵中的每个元素计算 dp 的值。

空间复杂度：$O(MN)$ 其中 M 和 M 是矩阵的行数和列数。创建了一个和原始矩阵一样大小的二维数组。

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int maximalSquare(char[][] matrix) {
        int maxSide = 0;
        int rows = matrix.length;
        int cols = matrix[0].length;
        if(matrix == null || rows == 0 || cols == 0){
            return maxSide;
        }
        int[][] dp = new int[rows][cols];
        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] = 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;
    }
}