221. 最大正方形

🟠   🔖  数组 动态规划 矩阵  🔗 力扣 LeetCode

题目

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

动态规划-状态压缩

/**
 * @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(n).fill(0);
	let prev = 0;

	// 动态规划遍历
	for (let i = 0; i < m; i++) {
		for (let j = 0; j < n; j++) {
			// 保留左上角的原始值，留到下一轮作为 prev 使用
			let temp = dp[j];
			if (matrix[i][j] == 1) {
				if (i == 0 || j == 0) {
					// base case
					dp[j] = 1;
				} else {
					dp[j] = Math.min(dp[j - 1], dp[j], prev) + 1;
				}
			} else {
				dp[j] = 0;
			}
			// prev 在下一轮迭代中使用，相当于 dp[i - 1][j - 1]
			prev = temp;
			// 更新最大正方形的边长
			res = Math.max(res, dp[j]);
		}
	}

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

相关题目

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