221. 最大正方形

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

这是一个经典的 最大正方形 动态规划问题。

---

思路分析

用 dp[i][j] 表示以 (i, j) 为右下角的最大正方形的边长。

状态转移方程：

如果 matrix[i][j] == '1':dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
否则:dp[i][j] = 0

解释：

• 以 (i, j) 为右下角的正方形，其大小受限于：
  • 上方能形成的正方形大小 dp[i-1][j]
  • 左方能形成的正方形大小 dp[i][j-1]
  • 左上方能形成的正方形大小 dp[i-1][j-1]
• 取三者最小值 + 1（当前格子本身）

---

算法步骤

1. 初始化 dp 数组，大小与 matrix 相同
2. 遍历每个格子 (i, j)：
   • 如果 matrix[i][j] == '1'：
     • 如果 i == 0 或 j == 0（第一行/列），dp[i][j] = 1
     • 否则 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
   • 否则 dp[i][j] = 0
3. 记录遍历过程中的最大边长 maxSide
4. 返回 maxSide * maxSide

---

代码实现

/*** @param {character[][]} matrix* @return {number}*/
var maximalSquare = function(matrix) {if (!matrix.length || !matrix[0].length) return 0;const m = matrix.length;const n = matrix[0].length;const dp = Array.from({ length: m }, () => Array(n).fill(0));let maxSide = 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) {dp[i][j] = 1;} else {dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1], dp[i-1][j-1]) + 1;}maxSide = Math.max(maxSide, dp[i][j]);}}}return maxSide * maxSide;
};

---

空间优化版

由于 dp[i][j] 只依赖于上一行和当前行的前一个元素，可以优化到 O(n) 空间：

var maximalSquare = function(matrix) {if (!matrix.length || !matrix[0].length) return 0;const m = matrix.length;const n = matrix[0].length;let dp = Array(n).fill(0);let maxSide = 0;let prev = 0; // 存储 dp[i-1][j-1]for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {const temp = dp[j]; // 保存给下一轮作为 previf (matrix[i][j] === '1') {if (i === 0 || j === 0) {dp[j] = 1;} else {dp[j] = Math.min(dp[j], dp[j-1], prev) + 1;}maxSide = Math.max(maxSide, dp[j]);} else {dp[j] = 0;}prev = temp;}}return maxSide * maxSide;
};

---

示例演示

例子：

matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]
]

DP 表（存储边长）：

1 0 1 0 0
1 0 1 1 1
1 1 1 2 2
1 0 0 1 0

最大边长 = 2，面积 = 4。

---

复杂度分析

• 时间复杂度：O(m × n) - 遍历整个矩阵
• 空间复杂度：
  • 基础版：O(m × n)
  • 优化版：O(n)

这是解决该问题的最优方法。