跳至主要內容

221. 最大正方形


221. 最大正方形

🟠   🔖  数组 动态规划 矩阵  🔗 力扣open in new window LeetCodeopen in new window

题目

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'.

题目大意

在一个由 '0''1' 组成的二维矩阵内,找到只包含 '1' 的最大正方形,并返回其面积。

解题思路

思路一:动态规划

  1. 动态规划:定义一个二维数组 dp,其中 dp[i][j] 表示以矩阵中第 i 行、第 j 列为右下角的正方形的最大边长。

  2. 状态转移方程:对于每个位置 (i, j),如果当前位置为 '1',则 dp[i][j] 的值取决于其左、上和左上三个相邻位置的最小值,因为只有这三个位置都为 '1',当前位置才能构成正方形。状态转移方程为:dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1

  3. 初始化:初始化第一行和第一列,因为这些位置没有左、上和左上相邻位置。

  4. 遍历计算:从矩阵的第二行和第二列开始遍历,根据状态转移方程计算每个位置的 dp 值。

  5. 结果dp 数组中的最大值即为最大正方形的边长,返回其面积。

复杂度分析

  • 时间复杂度: O(m * n),遍历整个矩阵。
  • 空间复杂度: O(m * n),使用了一个二维数组来存储中间状态。可以优化为 O(n)

思路二:动态规划-状态压缩

可以进行空间优化,将二维的 dp 数组优化为一维。因为在计算 dp[i][j] 的时候,只用到了 dp[i-1][j]dp[i][j-1],和 dp[i-1][j-1] 这三个位置的值,所以只需要维护当前行和上一行的状态即可。

动态规划状态转移方程变为:dp[j] = min(dp[j], dp[j-1], prev) + 1 ,其中:

  • dp[j] 对应 dp[i - 1][j],表示上边的格子的最大边长(此时 dp[j] 还未更新,仍保留着上一行的数据);
  • dp[j-1] 对应 dp[i][j - 1],表示左边的格子的最大边长(此时 dp[j - 1] 已经被更新,储存着本行最新的数据);
  • prev 对应 dp[i - 1][j - 1],表示左上边的格子的最大边长(在每次更新 dp[j] 之前,我们会保存 dp[j] 的原始值到 temp,然后在下一轮迭代中作为 prev 使用);

代码

动态规划
/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function (matrix) {
	let res = 0;
	const m = matrix.length;
	const n = matrix[0].length;
	const dp = new Array(m).fill(0).map(() => new Array(n).fill(0));

	// 动态规划遍历
	for (let i = 0; i < m; i++) {
		for (let j = 0; j < n; j++) {
			if (matrix[i][j] == 1) {
				if (i == 0 || j == 0) {
					// base case
					dp[i][j] = 1;
				} else {
					dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
				}
			}
			// 更新最大正方形的边长
			res = Math.max(res, dp[i][j]);
		}
	}

	// 返回最大正方形的面积
	return res * res;
};

相关题目

题号标题题解标签难度力扣
85最大矩形[✓] 数组 动态规划 2+🔴🀄️open in new window 🔗open in new window
764最大加号标志数组 动态规划🟠🀄️open in new window 🔗open in new window
2132用邮票贴满网格图贪心 数组 矩阵 1+🔴🀄️open in new window 🔗open in new window
2201统计可以提取的工件数组 哈希表 模拟🟠🀄️open in new window 🔗open in new window
2943最大化网格图中正方形空洞的面积数组 排序🟠🀄️open in new window 🔗open in new window