Links

0221. 最大正方形

题目地址(221. 最大正方形)

https://leetcode-cn.com/problems/maximal-square/

题目描述

在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。
示例:
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4

前置知识

  • 动态规划
  • 递归

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

221.maximal-square
符合直觉的做法是暴力求解处所有的正方形,逐一计算面积,然后记录最大的。这种时间复杂度很高。
我们考虑使用动态规划,我们使用 dp[i][j]表示以 matrix[i][j]为右下角的顶点的可以组成的最大正方形的边长。 那么我们只需要计算所有的 i,j 组合,然后求出最大值即可。
我们来看下 dp[i][j] 怎么推导。 首先我们要看 matrix[i][j], 如果 matrix[i][j]等于 0,那么就不用看了,直接等于 0。 如果 matrix[i][j]等于 1,那么我们将 matrix[[i][j]分别往上和往左进行延伸,直到碰到一个 0 为止。
如图 dp[3][3] 的计算。 matrix[3][3]等于 1,我们分别往上和往左进行延伸,直到碰到一个 0 为止,上面长度为 1,左边为 3。 dp[2][2]等于 1(之前已经计算好了),那么其实这里的瓶颈在于三者的最小值, 即Min(1, 1, 3), 也就是1。 那么 dp[3][3] 就等于 Min(1, 1, 3) + 1
221.maximal-square
dp[i - 1][j - 1]我们直接拿到,关键是往上和往左进行延伸, 最直观的做法是我们内层加一个循环去做就好了。 但是我们仔细观察一下,其实我们根本不需要这样算。 我们可以直接用 dp[i - 1][j]和 dp[i][j -1]。 具体就是Min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1
221.maximal-square
事实上,这道题还有空间复杂度 O(N)的解法,其中 N 指的是列数。 大家可以去这个leetcode 讨论看一下。

关键点解析

  • DP
  • 递归公式可以利用 dp[i - 1][j]和 dp[i][j -1]的计算结果,而不用重新计算
  • 空间复杂度可以降低到 O(n), n 为列数

代码

代码支持:Python,JavaScript:
Python Code:
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
res = 0
m = len(matrix)
if m == 0:
return 0
n = len(matrix[0])
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 if matrix[i - 1][j - 1] == "1" else 0
res = max(res, dp[i][j])
return res ** 2
JavaScript Code:
/*
* @lc app=leetcode id=221 lang=javascript
*
* [221] Maximal Square
*/
/**
* @param {character[][]} matrix
* @return {number}
*/
var maximalSquare = function (matrix) {
if (matrix.length === 0) return 0;
const dp = [];
const rows = matrix.length;
const cols = matrix[0].length;
let max = Number.MIN_VALUE;
for (let i = 0; i < rows + 1; i++) {
if (i === 0) {
dp[i] = Array(cols + 1).fill(0);
} else {
dp[i] = [0];
}
}
for (let i = 1; i < rows + 1; i++) {
for (let j = 1; j < cols + 1; j++) {
if (matrix[i - 1][j - 1] === "1") {
dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
max = Math.max(max, dp[i][j]);
} else {
dp[i][j] = 0;
}
}
}
return max * max;
};
复杂度分析
  • 时间复杂度:$O(M * N)$,其中 M 为行数,N 为列数。
  • 空间复杂度:$O(M * N)$,其中 M 为行数,N 为列数。