221. 最大正方形

发表于 分类于 阅读次数： Waline： 本文字数： 1.2k 阅读时长 ≈ 4 分钟

考点

  • 子矩形DP

思路

一、问题描述

给定一个仅包含字符 '0' 和 '1' 的二维矩阵 matrix，要求找出其中只包含 '1' 的最大正方形，并返回其面积。

二、动态规划建模思路

这是一个典型的 二维 DP（矩形 DP） 问题，其核心在于：

将“全局最大正方形”问题，转化为“以某个格子为锚点的局部最优”问题。

三、状态定义（关键）

定义二维状态： \[ f[i][j] = \text{以 }(i,j)\text{ 为右下角的、全为 1 的最大正方形边长} \] 注意三个关键词：

  • 以 \((i,j)\) 为右下角
  • 正方形
  • 边长（不是面积）

四、点阵示意：为什么选“右下角”

以 \((i,j)\) 作为右下角（记为 X）时，候选正方形形状如下：

1
2
3
■ ■ ■
■ ■ ■
■ ■ X

X 的三个依赖位置是：

  • 上：\((i-1, j)\)
  • 左：\((i, j-1)\)
  • 左上：\((i-1, j-1)\)

把它们画成一个 2×2 的局部邻域（最清晰且不易错位）：

1
2
3
4
5
6
7
8
(i-1, j-1)      (i-1, j)
     ↖               ↑
   [LU] ----------- [U]
     |               |
     |               |
   [L ] ----------- [X]
     ←               (i, j)
(i, j-1)

其中：

  • [X] 代表当前位置 \((i,j)\)（作为右下角）
  • [U] 代表上方 \((i-1,j)\)
  • [L] 代表左方 \((i,j-1)\)
  • [LU] 代表左上 \((i-1,j-1)\)

对应 DP 状态（若采用 \(f[i][j]\) 为右下角最大边长）：

  • 上：f[i-1][j]
  • 左：f[i][j-1]
  • 左上：f[i-1][j-1]

因此当 matrix[i][j] == '1' 时转移为： \[ f[i][j] = \min\big(f[i-1][j],\ f[i][j-1],\ f[i-1][j-1]\big) + 1 \] 当 matrix[i][j] == '0' 时： \[ f[i][j] = 0 \]

五、状态转移（核心公式）

1. 当前格为 '0'

如果 matrix[i][j] == '0'，那么它不可能作为任何全 1 正方形的右下角： \[ f[i][j] = 0 \]

2. 当前格为 '1'

如果 matrix[i][j] == '1'，则可以尝试在三个方向已有正方形的基础上“补一圈”： \[ f[i][j] = \min\big(f[i-1][j],\ f[i][j-1],\ f[i-1][j-1]\big) + 1 \]

六、点阵图直观理解 min + 1

示例：三个方向均为 1

1
2
3
dp 值分布：
1 1
1 X

说明左、上、左上都能支撑一个 \(1 \times 1\) 正方形 → 当前可以扩展成 \(2 \times 2\)

1
2
■ ■
■ ■

反例：左上是短板

1
2
3
dp 值分布：
3 3
3 X

但如果左上实际是：

1
2
1 3
3 X

则无法扩成 \(4 \times 4\)，只能到：

1
2
■ ■
■ ■

结论：

正方形能扩展到多大，取决于三个方向中的“最短板”。

七、答案的获取

由于 f[i][j] 存的是 边长，题目要求的是 面积，因此： \[ \text{答案} = \max_{i,j} f[i][j]^2 \] 遍历过程中维护最大边长即可。

八、实现方式一：二维 DP（直观版）

思路说明

  • 将 f 开成 (n+1) × (m+1)，第 0 行/列作为“虚拟边界”
  • 避免额外的边界判断
  • 时间复杂度：\(O(nm)\)
  • 空间复杂度：\(O(nm)\)

代码（已加注释）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        int ans = 0;

        // f[i][j]: 以 (i,j) 为右下角的最大正方形边长
        vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {

                // 当前格为 0，不可能形成正方形
                if (matrix[i - 1][j - 1] == '0')
                    continue;

                // 状态转移：取上、左、左上的最小值 + 1
                f[i][j] = min(
                    f[i - 1][j],
                    min(f[i][j - 1], f[i - 1][j - 1])
                ) + 1;

                ans = max(ans, f[i][j]);
            }
        }
        return ans * ans; // 返回面积
    }
};

九、实现方式二：滚动数组（空间优化）

优化动机

状态转移只依赖：

  • 当前行：f[i][j-1]
  • 上一行：f[i-1][j]、f[i-1][j-1]

因此可以用 两行滚动数组 将空间优化到 \(O(m)\)。

关键注意点

  1. 遇到 '0' 必须显式置 0 否则会残留上一行的旧值，污染结果。
  2. (i-1)&1 必须加括号 否则会触发 C++ 运算符优先级错误。

代码（已加注释）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        int ans = 0;

        // 只保留两行：当前行和上一行
        vector<vector<int>> f(2, vector<int>(m + 1, 0));

        for (int i = 1; i <= n; ++i) {
            int cur = i & 1;          // 当前行
            int pre = (i - 1) & 1;    // 上一行

            for (int j = 1; j <= m; ++j) {

                // 当前格为 0，必须清零
                if (matrix[i - 1][j - 1] == '0') {
                    f[cur][j] = 0;
                    continue;
                }

                // 取 上 / 左 / 左上 三个方向的最小值
                f[cur][j] = min(
                    f[pre][j],
                    min(f[cur][j - 1], f[pre][j - 1])
                ) + 1;

                ans = max(ans, f[cur][j]);
            }
        }
        return ans * ans; // 返回面积
    }
};

十、总结

  • 本题是 二维 DP 的经典入门题
  • 核心在于：
    • 合理的状态定义（“以某点为右下角”）
    • 利用局部信息决定全局结构
  • min(上, 左, 左上) + 1 是矩形 DP 中极具代表性的转移模式
  • 滚动数组是二维 DP 向一维压缩的重要技巧