.jpg)
436 字
2 分钟
最大正方形
.png)
题目描述
在一个由 '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；否则为0。 - 初始化： 首行和首列直接复制
matrix值（转换为数字）。 - 更新结果： 遍历过程记录最大边长，结果 = 最大边长²。
关键洞察
- 右下角核心： 以
(i,j)为右下角的正方形边长，由左上、上、左三个相邻点的最小值决定（短板效应）。 - 几何约束： 状态转移方程保证区域内全为 ‘1’（取最小值扩展时不会覆盖 ‘0’）。
- 空间优化：
dp数组可降维至 O(n)（仅需保存上一行和当前行前一列）。
复杂度分析
- 时间复杂度：O(m×n) 遍历矩阵每个元素一次。
- 空间复杂度：
- 基础版：O(m×n)（二维
dp数组） - 优化版：O(n)（一维数组，
n为列数）
- 基础版：O(m×n)（二维
代码实现
/** * @param {character[][]} matrix * @return {number} */var maximalSquare = function (matrix) { if (!matrix || matrix.length === 0 || matrix[0].length === 0) return 0 const m = matrix.length, n = matrix[0].length let maxSide = 0 const dp = new Array(n + 1).fill(0) let prev = 0 for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { let temp = dp[j] if (matrix[i - 1][j - 1] === '1') { dp[j] = Math.min(dp[j], dp[j - 1], prev) + 1 maxSide = Math.max(maxSide, dp[j]) } else { dp[j] = 0 } prev = temp } prev = 0 } return maxSide * maxSide}