📃 题目描述

题目链接：221. 最大正方形 (opens new window)

🔔 解题思路

class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        
        int row = matrix.length;
        int col = matrix[0].length;
        // dp[i][j] 表示以 matrix[i][j] 为右下角的最大正方形的边长
        int[][] dp = new int[row][col];

        int maxEdge = 0;
        for (int i = 0; i < row; i ++) {
            for (int j = 0; j < col; 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;
                    }
                }

                maxEdge = Math.max(maxEdge, dp[i][j]);
            }
        }

        return maxEdge * maxEdge;
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：