返回介绍

solution / 0200-0299 / 0221.Maximal Square / README_EN

发布于 2024-06-17 01:04:03 字数 5113 浏览 0 评论 0 收藏 0

221. Maximal Square

中文文档

Description

Given an m x n binary matrix filled with 0's and 1's, _find the largest square containing only_ 1's _and return its area_.

 

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Example 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

Example 3:

Input: matrix = [["0"]]
Output: 0

 

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] is '0' or '1'.

Solutions

Solution 1: Dynamic Programming

We define $dp[i + 1][j + 1]$ as the maximum square side length with the lower right corner at index $(i, j)$. The answer is the maximum value among all $dp[i + 1][j + 1]$.

The state transition equation is:

$$ 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} $$

The time complexity is $O(m\times n)$, and the space complexity is $O(m\times n)$. Where $m$ and $n$ are the number of rows and columns of the matrix, respectively.

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;
  }
}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文