LeetCode 221. 最大正方形

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

✅ 221. 最大正方形

思路分析

解法一：动态规划（推荐）

核心思路：

状态定义：dp[i][j] 表示以 (i, j) 为右下角能构成的最大全为 1 的正方形边长。

状态转移：

若 matrix[i][j] == '0'：dp[i][j] = 0，当前格为 0，无法构成正方形。

若 matrix[i][j] == '1'：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

dp[i-1][j]：上方最大正方形边长，限制当前列的高度

dp[i][j-1]：左方最大正方形边长，限制当前行的宽度

dp[i-1][j-1]：左上角最大正方形边长，限制对角延伸

三者取最小（木桶效应），再 +1 即为当前可扩展的边长

直觉理解：想象从右下角向左上方扩展正方形，必须三个方向都”够大”才能再扩一格；任意一方向不足则受限于该方向。

答案：遍历 dp 数组取最大边长 maxSide，面积为 maxSide²。

边界处理：使用 (m+1) × (n+1) 的 dp 数组，第 0 行和第 0 列初始化为 0，避免越界判断。

复杂度分析：

时间复杂度：O(m × n)，其中 m、n 分别为矩阵的行数和列数

空间复杂度：O(m × n)，使用二维 dp 数组；可用滚动数组优化至 O(n)

class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        // dp[i][j] 表示以 (i-1, j-1) 为右下角的最大全1正方形边长，多一行一列避免边界判断
        int[][] dp = new int[m + 1][n + 1];
        int maxSide = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    // 取左、上、左上三方向最小值加 1
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        return maxSide * maxSide;
    }
}

func maximalSquare(matrix [][]byte) int {
    m, n := len(matrix), len(matrix[0])
    // dp[i][j] 表示以 (i-1, j-1) 为右下角的最大全1正方形边长，多一行一列避免边界判断
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    maxSide := 0
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if matrix[i-1][j-1] == '1' {
                // 取左、上、左上三方向最小值加 1
                dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1
                if dp[i][j] > maxSide {
                    maxSide = dp[i][j]
                }
            }
        }
    }
    return maxSide * maxSide
}

相似题目

题目	难度	考察点
85. 最大矩形	困难	单调栈 + 动态规划
1277. 统计全为 1 的正方形子矩阵	中等	二维动态规划
1139. 最大的以 1 为边界的正方形	中等	二维动态规划
62. 不同路径	中等	二维动态规划
64. 最小路径和	中等	二维动态规划
304. 二维区域和检索 - 矩阵不可变	中等	二维前缀和
764. 最大加号标志	中等	二维动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/20077268