第一题、221.最大正方形

方法一、暴力法
由于正方形的面积等于边长的平方，因此要找到最大正方形的面积，首先需要找到最大正方形的边长，然后计算最大边长的平方即可。
暴力法思路：
遍历矩阵中的每个元素，每次遇到 1，则将该元素作为正方形的左上角；
确定正方形的左上角后，根据左上角所在的行和列计算可能的最大正方形的边长（正方形的范围不能超出矩阵的行数和列数），在该边长范围内寻找只包含 1 的最大正方形；
每次在下方新增一行以及在右方新增一列，判断新增的行和列是否满足所有元素都是 1。

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        # 如果矩阵为空或第一行为空，则返回 0
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return 0
        
        maxSide = 0  # 初始化最大正方形的边长为 0
        rows, columns = len(matrix), len(matrix[0])  # 获取矩阵的行数和列数
        
        # 遍历矩阵中的每个元素
        for i in range(rows):
            for j in range(columns):
                if matrix[i][j] == '1':  # 如果当前元素为 '1'
                    maxSide = max(maxSide, 1)  # 至少可以构成边长为 1 的正方形
                    currentMaxSide = min(rows - i, columns - j)  # 计算可能的最大正方形边长
                    
                    # 检查以当前元素为左上角的正方形区域
                    for k in range(1, currentMaxSide):
                        flag = True  # 标志变量，用于判断新增的一行和一列是否全部为 '1'
                        
                        if matrix[i + k][j + k] == '0':  # 如果对角线元素为 '0'，则无法继续扩展正方形
                            break
                        
                        # 检查新增的第 k 行和第 k 列是否全部为 '1'
                        for m in range(k):
                            if matrix[i + k][j + m] == '0' or matrix[i + m][j + k] == '0':
                                flag = False  # 如果发现 '0'，设置标志变量为 False
                                break
                        
                        if flag:  # 如果新增的行和列全部为 '1'
                            maxSide = max(maxSide, k + 1)  # 更新最大正方形边长
                        else:
                            break  # 如果不满足条件，则跳出循环
        
        maxSquare = maxSide * maxSide  # 计算最大正方形的面积
        return maxSquare  # 返回最大正方形的面积

用时

用Python超出了时间限制，用Java可以accept，但是时间复杂度很差，以下是Java代码：

class Solution {
    public int maximalSquare(char[][] matrix) {
        int maxSide = 0;
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return maxSide;
        }
        int rows = matrix.length, columns = matrix[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    // 遇到一个 1 作为正方形的左上角
                    maxSide = Math.max(maxSide, 1);
                    // 计算可能的最大正方形边长
                    int currentMaxSide = Math.min(rows - i, columns - j);
                    for (int k = 1; k < currentMaxSide; k++) {
                        // 判断新增的一行一列是否均为 1
                        boolean flag = true;
                        if (matrix[i + k][j + k] == '0') {
                            break;
                        }
                        for (int m = 0; m < k; m++) {
                            if (matrix[i + k][j + m] == '0' || matrix[i + m][j + k] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        if (flag) {
                            maxSide = Math.max(maxSide, k + 1);
                        } else {
                            break;
                        }
                    }
                }
            }
        }
        int maxSquare = maxSide * maxSide;
        return maxSquare;
    }
}

Java用时和内存

时空复杂度

此方法需要注意在判断边界条件时的：

        if len(matrix) == 0 or len(matrix[0]) == 0:
            return 0

此判断是检查矩阵的第一行是否为空（即是否有列）。如果没有任何列元素，也说明无法构成任何正方形，因此直接返回0。
第二个判断条件容易忽视。

方法二、动态规划
方法一时间复杂度太高，可以使用动态规划降低时间复杂度。用 dp(i,j) 表示以 (i,j) 为右下角，且只包含 1 的正方形的边长最大值。如果能计算出所有 dp(i,j) 的值，那么其中的最大值即为矩阵中只包含 1 的正方形的边长最大值，其平方即为最大正方形的面积。
那么如何计算 dp 中的每个元素值呢？对于每个位置 (i,j)，检查在矩阵中该位置的值：
如果该位置的值是 0，则 dp(i,j)=0，因为当前位置不可能在由 1 组成的正方形中；
如果该位置的值是 1，则 dp(i,j) 的值由其上方、左方和左上方的三个相邻位置的 dp 值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加 1，状态转移方程如下：
dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1
边界条件：如果 i 和 j 中至少有一个为 0，则以位置 (i,j) 为右下角的最大正方形的边长只能是 1，因此 dp(i,j)=1。
实例：原始矩阵如下：

0 1 1 1 0
1 1 1 1 0
0 1 1 1 1
0 1 1 1 1
0 0 1 1 1

对应的 dp 值如下:

0 1 1 1 0
1 1 2 2 0
0 1 2 3 1
0 1 2 3 2
0 0 1 2 3

计算dp值的过程

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        # 如果矩阵为空或者第一行为空，直接返回 0
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return 0
        
        maxSide = 0  # 初始化最大正方形的边长为 0
        rows, columns = len(matrix), len(matrix[0])  # 获取矩阵的行数和列数
        
        # 初始化动态规划数组，dp[i][j] 表示以 (i, j) 为右下角的最大正方形边长
        dp = [[0] * columns for _ in range(rows)]
        
        # 遍历矩阵的每个元素
        for i in range(rows):
            for j in range(columns):
                if matrix[i][j] == '1':  # 如果当前元素是 '1'
                    if i == 0 or j == 0:
                        # 如果在第一行或第一列，最大正方形边长只能是 1
                        dp[i][j] = 1
                    else:
                        # 否则，状态转移方程，取左边、上边和左上角的最小值 + 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])
        
        maxSquare = maxSide * maxSide  # 计算最大正方形的面积
        return maxSquare  # 返回最大正方形的面积

用时和内存

1. 以右下角为基准的优点：

• 状态转移更自然：
  • 在动态规划中，通常从前向后（左到右、上到下）遍历矩阵。使用右下角作为基准点时，dp[i][j] 可以通过它的左边(dp[i][j-1])、上边(dp[i-1][j])和左上角(dp[i-1][j-1])的值来计算。这三个值已经在之前的迭代中计算过，因此转移方程自然且简洁：
    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
• 避免复杂性：
  • 如果以 (i, j) 为左上角来考虑最大正方形的边长，计算dp[i][j]时，需要向右和向下扩展来确认是否存在一个完全由'1'组成的正方形。这种方法需要在每个位置执行额外的检查和多次扫描，增加了时间复杂度。

2. 以左上角为基准的缺点：

• 状态转移更复杂：
  • 要以 (i, j) 为左上角来计算最大正方形的边长，需要在每一步确认下方和右方的所有点是否为 '1'。这意味着需要额外的双重循环检查：

    # 伪代码示例，表示以 (i, j) 为左上角的最大正方形边长
    for size in range(1, possible_max_size):
        for k in range(size):
            if matrix[i + size][j + k] == '0' or matrix[i + k][j + size] == '0':
                break
    

  • 这种方法会导致在大矩阵中处理复杂度急剧增加，并可能导致超时问题。

3. 空间效率和易于理解：

• 以右下角为基准更节省空间：
  • 只需要一个二维dp数组，空间复杂度为 O(m * n)（其中 m 为行数，n 为列数）。
  • 以左上角为基准，需要维护更多的状态信息，可能会使实现变得复杂。