最大正方形

最大正方形的状态如何定义？

• 问题: 在只含 0、1 的矩阵中求只含 1 的最大正方形面积 (221);
• 阶段: 按正方形的右下角坐标划分;
• 状态: dp[i][j] 为以 [i, j] 为右下角的最大全 1 正方形边长;
• 答案: max(dp[i][j])^2, 需要单独维护最大值;

转移方程如何写？

• 当前格为 0: 不可能作为正方形右下角, dp[i][j] = 0;
• 当前格为 1: 边长受上方、左方、左上方三个状态的最小值约束;
  • 方程: dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1;
• 几何解释: 三者取最小保证新扩展的一行一列全部为 1;
• 初值: 首行首列遇到 1 时为 1 (正方形边长为 1);

const maximalSquare = (matrix) => {
  const rows = matrix.length;
  const cols = matrix[0].length;
  const dp = Array.from({ length: rows }, () => new Array(cols).fill(0));
  let side = 0;
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (matrix[i][j] === "0") continue;
      if (i === 0 || j === 0) dp[i][j] = 1;
      else dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
      side = Math.max(side, dp[i][j]);
    }
  }
  return side * side;
};

为什么不能只取上方和左方的最小值？

• 反例: 上方与左方都有长度 2 的正方形, 但左上方只有长度 1, 新正方形会被左上方的缺口截断;
• 结论: 必须同时对左上角取最小值, 三个方向共同决定能扩展的边长;
• 复杂度: 时间 O(mn), 空间 O(mn);

最大矩形和最大正方形有什么区别？

• 最大正方形: 状态表示边长, 三个方向取最小;
• 最大矩形: 需要按每行统计柱状图高度, 再对每行求柱状图最大矩形 (单调栈), 状态维度不同;