Question

221. 最大正方形

English Version

题目描述

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

解法

方法一：动态规划

我们定义 $dp[i + 1][j + 1]$ 表示以下标 $(i, j)$ 作为正方形右下角的最大正方形边长。答案为所有 $dp[i + 1][j + 1]$ 中的最大值。

状态转移方程为：

$$ dp[i + 1][j + 1] = \begin{cases} 0 & \text{if } matrix[i][j] = '0' \ \min(dp[i][j], dp[i][j + 1], dp[i + 1][j]) + 1 & \text{if } matrix[i][j] = '1' \end{cases} $$

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

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

class Solution {
  public int maximalSquare(char[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int[][] dp = new int[m + 1][n + 1];
    int mx = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (matrix[i][j] == '1') {
          dp[i + 1][j + 1] = Math.min(Math.min(dp[i][j + 1], dp[i + 1][j]), dp[i][j]) + 1;
          mx = Math.max(mx, dp[i + 1][j + 1]);
        }
      }
    }
    return mx * mx;
  }
}

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

func maximalSquare(matrix [][]byte) int {
  m, n := len(matrix), len(matrix[0])
  dp := make([][]int, m+1)
  for i := 0; i <= m; i++ {
    dp[i] = make([]int, n+1)
  }
  mx := 0
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if matrix[i][j] == '1' {
        dp[i+1][j+1] = min(min(dp[i][j+1], dp[i+1][j]), dp[i][j]) + 1
        mx = max(mx, dp[i+1][j+1])
      }
    }
  }
  return mx * mx
}

public class Solution {
  public int MaximalSquare(char[][] matrix) {
    int m = matrix.Length, n = matrix[0].Length;
    var dp = new int[m + 1, n + 1];
    int mx = 0;
    for (int i = 0; i < m; ++i)
    {
      for (int j = 0; j < n; ++j)
      {
        if (matrix[i][j] == '1')
        {
          dp[i + 1, j + 1] = Math.Min(Math.Min(dp[i, j + 1], dp[i + 1, j]), dp[i, j]) + 1;
          mx = Math.Max(mx, dp[i + 1, j + 1]);
        }
      }
    }
    return mx * mx;
  }
}