InterviewGuide 刷题笔记:LeetCode 221「最大正方形」——二维矩阵 DP 递推式推导与 C++ 实现
InterviewGuide 刷题笔记:LeetCode 221「最大正方形」——二维矩阵 DP 递推式推导与 C++ 实现
本篇技术指南基于 InterviewGuide 仓库中精选力扣 300+ 题之动态规划系列下的 221.最大正方形 题解,以该题为核心讲解如何在仅含 0/1 的二维矩阵中通过动态规划求出"只包含 1 的最大正方形面积"。读完本文你将掌握:如何定义二维 DP 状态、如何推导"右下角递推"的转移方程、如何处理边界条件,以及如何用滚动数组将空间复杂度从 O(m×n) 降到 O(n)。
一、题目回顾:在 0/1 矩阵中找最大全 1 正方形
题目要求在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。
示例:
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4
示例中最大的全 1 正方形位于矩阵右下区域(第 2~3 行、第 3~4 列),边长为 2,面积为 4。
该题在 InterviewGuide 仓库中归类于动态规划 Medium 等级,是"二维矩阵 + 递推"这一类 DP 题型的代表之一。仓库作者在力扣刷题专栏说明中明确这套题解面向校招、社招求职笔试面试而非算法竞赛,因此本文也以"面试中能快速写对、讲清原理"为第一目标。
二、思路分析:为什么暴力枚举不可取,DP 如何切入
最容易想到的暴力做法是:枚举每个格子作为正方形的左上角,再枚举边长,逐行逐列检查是否全为 1。设矩阵大小为 m×n、最大边长为 k,则时间复杂度可到 O(m·n·k²),在较大矩阵下不可接受。
把问题换个角度想:一个"以 (i, j) 为右下角、边长为 len"的正方形全为 1,等价于同时满足三个条件:
- 以
(i-1, j)为右下角、边长为len-1的正方形全为 1; - 以
(i, j-1)为右下角、边长为len-1的正方形全为 1; - 以
(i-1, j-1)为右下角、边长为len-1的正方形全为 1; - 且
matrix[i][j]本身为1。
换句话说,如果这三块子正方形里有一块边长不足 len-1,那么以 (i,j) 为右下角的正方形边长必然撑不满 len。这正是"短板效应":最大可行边长 = 三者最小值 + 1。由此可以得到清晰的 DP 递推关系。
三、状态定义与转移方程推导
3.1 状态定义
定义 dp[i][j] 表示以 (i, j) 为右下角的最大全 1 正方形的边长。由于我们只需要统计面积,最终答案取所有 dp[i][j] 的最大值再平方即可。
3.2 转移方程
对于 matrix[i][j] == '1' 的格子:
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
推导逻辑:以 (i,j) 为右下角、边长为 dp[i][j] 的正方形要全为 1,那么它的左上角三个邻域位置(正上、正左、左上)各自作为右下角时,至少都要能撑起边长为 dp[i][j] - 1 的全 1 正方形。三者中最小的一方就是瓶颈,所以取 min 再加 1。
3.3 边界条件
- 当
i == 0或j == 0(第一行、第一列)时,以该格子为右下角最多只能形成边长为 1 的正方形,因此只要matrix[i][j] == '1',dp[i][j] = 1; - 当
matrix[i][j] == '0'时,dp[i][j] = 0(不参与计算,保持初值)。
3.4 为什么这样一定正确
因为 DP 自左上向右下逐格推进,计算 dp[i][j] 时其依赖的 dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1] 均已在上一轮循环中算出,满足"无后效性 + 最优子结构"两个 DP 适用条件,转移方程的正确性由子问题的正确性保证。
四、完整 C++ 实现(继承原题解并逐行注释)
原文档给出的第一版实现如下,它在所有 cpp 提交中执行用时 20 ms、击败 79.27% 的用户,内存消耗 11.1 MB、击败 62.99% 的用户。这里保留原代码的算法骨架,并补充完整注释便于面试讲解:
int maximalSquare(vector<vector<char>>& matrix) {
// 空矩阵直接返回 0,注意 matrix[0].empty() 的判断避免越界
if (matrix.empty() || matrix[0].empty()) return 0;
int m = matrix.size(), n = matrix[0].size();
int length = 0; // 记录全局最大边长
// dp 数组:res[i][j] 表示以 (i,j) 为右下角的最大全1正方形边长
vector<vector<int>> res(m, vector<int>(n, 0));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == '1') { // 只有值为 1 的格子才可能构成正方形
if (i == 0 || j == 0) {
// 边界行/列:最多只能形成边长 1 的正方形
res[i][j] = 1;
} else {
// 核心转移方程:左上、正上、正左三者的最小值 + 1
res[i][j] = min(min(res[i - 1][j - 1], res[i - 1][j]), res[i][j - 1]) + 1;
}
// 随时更新全局最大边长
length = max(length, res[i][j]);
}
}
}
// 边长平方即面积
return pow(length, 2);
}
关键点说明:
- 输入类型是
vector<vector<char>>,元素为字符'1'/'0',因此判断必须写成matrix[i][j] == '1'(字符常量),而不能与整数1比较; - 返回值
pow(length, 2)是 double 类型,函数签名返回 int 时会隐式转换,面试时也可以直接写length * length更严谨; - 两层循环中
i == 0 || j == 0的特判正好覆盖第一行与第一列,配合min(min(...))的嵌套调用,代码简洁且无需为 dp 数组额外多开一行一列。
复杂度分析
- 时间复杂度:O(m×n),每个格子只被访问一次,相比暴力枚举有本质提升;
- 空间复杂度:O(m×n),使用了一个与原矩阵同尺寸的二维
res数组。
五、空间优化:滚动数组把 O(m×n) 降到 O(n)
观察转移方程可以发现,dp[i][j] 只依赖当前行的左邻居 dp[i][j-1]、上一行的同列 dp[i-1][j] 和 上一行的左邻居 dp[i-1][j-1],也就是说计算第 i 行时只需要保留第 i-1 行的完整信息。因此可以用一维数组滚动更新:
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int m = matrix.size(), n = matrix[0].size();
vector<int> dp(n, 0); // 滚动数组,保存"上一行"的 dp 值
int length = 0, prev = 0; // prev 记录左上角 dp[i-1][j-1]
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int temp = dp[j]; // 先保存旧值,作为下一格的"左上角"
if (matrix[i][j] == '1') {
if (i == 0 || j == 0) {
dp[j] = 1;
} else {
dp[j] = min(min(prev, dp[j]), dp[j - 1]) + 1;
// prev = dp[i-1][j-1],dp[j] = dp[i-1][j],dp[j-1] = dp[i][j-1]
}
length = max(length, dp[j]);
} else {
dp[j] = 0; // 值为 0 的格子必须清零,防止污染下一行
}
prev = temp; // 更新左上角引用
}
}
return length * length;
}
空间优化版将内存消耗从 O(m×n) 降至 O(n),当矩阵行数很大时收益明显。需要注意 prev 变量在每个内层循环末尾更新的顺序,这是滚动数组最容易写错的地方。
六、延伸:与仓库内同类 DP 题的关联
本题的递推思想在仓库的动态规划题单中还有两个"近亲":
-
1277. 统计全为 1 的正方形子矩阵:状态转移式与本题几乎一致(
matrix[i][j] += min({matrix[i-1][j-1], matrix[i][j-1], matrix[i-1][j]})),只是它要求统计所有边长不同的全 1 正方形个数而非最大面积。由 DP 定义可知,dp[i][j] = k恰好意味着以(i,j)为右下角同时存在边长 1~k 的 k 个正方形,因此对每个dp[i][j]累加即可得到总数。两道题放到一起对比学习,能更深刻理解"最大边长 dp"这个状态的威力; -
152. 乘积最大子序列:仓库文档在该题末尾留有"最大正方形"锚点跳转,两题都展示了如何通过"以某个位置结尾"的状态定义把看似复杂的问题线性化解——一维是
d[i]/e[i]两个状态滚动,二维则是dp[i][j]与三个邻居递推。
此外,动态规划目录的心得总结中提到字符匹配类问题常用"多开一格 + 画表格"的技巧,而本题这类矩阵类 DP 同样非常推荐先在纸上把 dp 表格手推一遍:从左上角开始,按公式一格一格填,很快就能验证 min 三选一的正确性。
七、小结:面试作答要点
在面试中讲解本题时,建议按以下逻辑组织答案,这也正是本仓库该题解所体现的思考路径:
- 先说暴力思路及其缺陷,给出 O(m·n·k²) 的复杂度估算;
- 定义状态:
dp[i][j]为以(i,j)为右下角的最大全 1 正方形边长; - 推导转移方程:
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1,并解释"短板效应"; - 交代边界:第一行/第一列只能取 1,值为 0 的格子为 0;
- 给出代码与复杂度:O(m×n) 时间、O(m×n) 空间,可优化到 O(n);
- 主动延伸:提到 1277 题的"统计个数"变体,展示你对这一类问题的系统掌握。
该题解收录于 InterviewGuide 仓库的精选力扣 300+ 道算法题系列,适合校招、社招求职者与转行者作为面试前刷题复习材料。