Medium

题目描述

在一个由 '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'

解题思路

这是一道经典的动态规划题目，核心思想是找出以每个位置为右下角的最大正方形边长。

解题思路：

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

  2. 状态转移方程：

    • 如果 matrix[i][j] == '0'，则 dp[i][j] = 0
    • 如果 matrix[i][j] == '1'，则 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

  3. 转移方程解释：要形成一个边长为 k 的正方形，当前位置的左边、上边、左上角都必须至少能形成边长为 k-1 的正方形。因此取三者最小值加1。

  4. 优化空间：由于状态转移只依赖于前一行和当前行的前一个元素，可以用一维数组优化空间复杂度。

  5. 边界处理：第一行和第一列的值直接等于原矩阵对应位置的值。

这种方法避免了暴力枚举所有可能正方形的高时间复杂度，通过动态规划在一次遍历中完成计算。

代码实现

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        int maxSide = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
                    }
                    maxSide = max(maxSide, dp[i][j]);
                }
            }
        }
        
        return maxSide * maxSide;
    }
};

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * n for _ in range(m)]
        max_side = 0
        
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == '1':
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                    max_side = max(max_side, dp[i][j])
        
        return max_side * max_side

public class Solution {
    public int MaximalSquare(char[][] matrix) {
        int m = matrix.Length, n = matrix[0].Length;
        int[,] dp = new int[m, n];
        int maxSide = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; 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;
    }
}

var maximalSquare = function(matrix) {
    if (!matrix || matrix.length === 0 || matrix[0].length === 0) return 0;
    
    const m = matrix.length;
    const n = matrix[0].length;
    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
    let maxSide = 0;
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (matrix[i-1][j-1] === '1') {
                dp[i][j] = 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;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m×n)需要遍历整个矩阵一次，每个位置的计算为常数时间
空间复杂度O(m×n)使用二维DP数组存储状态，可优化至O(n)

相关题目