LeetCode 221 最大正方形这道题几乎每隔一阵子就会出现在我的面试复盘帖、刷题打卡群或者一对一模拟面试里。第一次见到它的人十有八九会以为“不就是找最大的一块 1 吗”结果真上手一写边界条件和递推关系能把自己绕晕。也有很多人背下了dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1这个公式但面试官只要追问一句“为什么是 min 而不是 max”就当场卡壳。这篇文章我会从暴力思路开始拆把 DP 递推式背后的几何直觉、二维转一维滚动数组的细节、以及实际刷题和面试里的高频坑全部讲透最后再把 221 这个题扩展到 85、1277 这一整个“全 1 矩阵”家族。不管是刚入门动态规划的同学还是准备社招想补基础的开发者这篇应该都能给到一些实在的东西。1. 拿题先别急写代码把约束和暴力思路盘清楚1.1 题面拆解与两个隐藏陷阱题目的描述非常简短给你一个m x n的矩阵矩阵元素是0和1请你找到只包含1的最大正方形返回它的面积。很多人在这一步就开始犯第一个错误把“正方形”和“矩形”混为一谈。正方形要求边长相等这是整道题最大的简化也是 DP 方案成立的根本原因。如果题目问的是最大矩形那就是另一道难度完全不同的题LeetCode 85解法思路会从三格 min 变成单调栈或悬线法。所以做题前第一件事就是把“正方形”这个约束刻在脑子里。第二个隐藏陷阱是矩阵元素的类型。LeetCode 给的是字符矩阵1带引号很多从 C/C 转过来的朋友会下意识写matrix[i][j] 1结果整个判断全部失配输出永远是 0。这个 bug 非常隐蔽因为编译器不会报错只有对拍测试数据时才会暴露。我习惯在写代码前先确认matrix[i][j] 1还是matrix[i][j] 1这点在下面所有代码里都会贯彻。说句实在话这个题的题面信息量不大真正有价值的是它背后的模型。你要找的正方形必须是一个区域内所有格子全为 1且形状必须是正方形。这意味着我们可以用一个唯一参数来描述它——边长。面积就是边长的平方所以问题的核心就变成了如何高效地在矩阵里找到可能的最大边长。1.2 暴力解法先建立一个“校验器”暴力思路不难想枚举每个可能的左上角坐标(i, j)再枚举边长k检查从(i, j)到(ik-1, jk-1)这个k x k区域是否全为 1。如果全为 1就用k * k更新答案。检查一个区域是否全为 1最笨的办法是再开一个循环逐个格子看这样整体复杂度会到夸张的 O(m * n * min(m, n) * k^2)。更合理的方式是引入二维前缀和先预处理出sum[i][j]表示从(0, 0)到(i, j)的矩阵内 1 的个数然后判断区域和是否等于k * k。区域和的公式是sum[i][j] - sum[i-k][j] - sum[i][j-k] sum[i-k][j-k]等于k * k就说明这个区域全为 1。这样暴力枚举的复杂度是 O(m * n * min(m, n))在 300 x 300 的矩阵上勉强能跑1000 x 1000 就会超时。我写暴力不是为了让你用它交题而是因为它在调试时是一个绝佳的“对数器”。你可以先写一个保证正确的暴力版本再写 DP 版本然后随机生成矩阵对比两者输出。如果 DP 结果和暴力不一致说明优化代码有 bug。这个习惯帮我节省过大量排查时间尤其是滚动数组写法刚上手时没有暴力版对照真不敢说一次写对。2. DP 的核心dp[i][j] 这个格子到底在回答什么问题2.1 状态定义与三个限定词动态规划的第一步永远是定义状态。这题教科书级的定义是dp[i][j]表示以坐标(i, j)为右下角的最大全 1 正方形边长。注意限定词有三个右下角、最大、边长。先说“右下角”为什么要用右下角而不是左上角因为我们的遍历顺序是从上到下、从左到右当处理到(i, j)时它的上方、左方、左上方的格子的 dp 值都已经计算完毕。这种“只依赖已计算部分”的性质在动态规划里叫无后效性。如果你改成以左上角定义递推方向就会变得别扭。再说“边长”而不是“面积”。面积 边长²两者单调对应但存边长有两个好处一是避免在状态转移里开根号二是避免你最后返回的数值和 dp 值混淆。很多人最后错误地返回了maxSide而不是maxSide * maxSide就是因为状态定义里存的是面积思维混乱了。统一存边长是最保险的做法。这个状态定义的直觉来源其实特别朴素matrix[i][j] 1时这个格子至少自己就能构成一个边长 1 的正方形所以 dp 值至少是 1。如果我想让以它为右下角的正方形更大就必须把它左边、上边、左上边的邻居们“已有的成果”拼起来。问题就变成了三块成果怎么拼才能拼出一个更大的正方形。2.2 为什么取 min三块木板与短板效应先给出完整递推式if matrix[i][j] 0: dp[i][j] 0 else if i 0 or j 0: dp[i][j] 1 else: dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1很多人不理解的是min。我用一个木桶类比来解释假设你要以(i, j)为右下角拼出一个边长为 k 的正方形那么这个正方形的最上面一行必须依赖上一行的格子最左边一列必须依赖左边一列的格子左上角的内部区域必须依赖左上方向的格子。具体来说dp[i-1][j]管的是“上面能延伸多少”dp[i][j-1]管的是“左边能延伸多少”dp[i-1][j-1]管的是“左上角那块区域能作多大底座”。正方形要求三个方向同步到位任何一个方向长度不够整个正方形就拼不出来。所以能取的最大边长只会等于这三者里的最小值加一而不是最大值加一。举个例子假设dp[i-1][j] 5dp[i][j-1] 5但dp[i-1][j-1] 1那以(i, j)为右下角的正方形边长最多是 2。因为左上角那块只有边长 1 的全 1 底座你不可能凭空让左上角区域扩展成边长 4 的正方形。这就像木桶装水水量取决于最短的那块板。再给出一个更严密的双向证明框架。正向如果以(i, j)为右下角存在边长为 k 的全 1 正方形那么去掉最下面一行和最右边一列后剩下的是边长为 k-1 的全 1 正方形而这个剩余正方形分别被(i-1, j)、(i, j-1)、(i-1, j-1)这三个格子为右下角的全 1 区域覆盖所以这三个位置的 dp 值至少都是 k-1。反向如果dp[i-1][j] k-1、dp[i][j-1] k-1、dp[i-1][j-1] k-1那么这三个方向分别能提供边长为 k-1 的全 1 正方形把它们和右下角那个1拼在一起就能得到一个边长为 k 的全 1 正方形。两个方向一夹dp[i][j] min(...) 1的等号关系就成立了。这是我在面试时让面试官点头的关键论证。2.3 边界条件与 dp 表的构建顺序首行和首列需要单独处理i 0或j 0时以它们为右下角的正方形最多只能是自己这一个格子因为再往上或往左没有空间了。所以只要matrix[i][j] 1dp 值直接置 1。如果你在边界处硬套递推式去访问dp[-1][j]之类的下标就会数组越界。LeetCode 的测试数据里经常出现单行、单列的极端输入这块判断必须从第一步就做好。遍历顺序必须是外层行、内层列或者反过来按列遍历也行但一定是“从左上到右下”。每算出一个dp[i][j]就用它更新全局最大值maxSide。最后返回maxSide * maxSide。这里我强烈建议一个练习方法在草稿纸上画一个 4x4 的矩阵把 dp 表一行一行填出来。比如全 1 矩阵的 dp 表就是1 1 1 1 1 2 2 2 1 2 3 3 1 2 3 4看到那个斜向递增的对角线了吗填完表你就能直观感觉到“边长从左上角往右下角扩散”的动态过程。这个方法不仅适合 221也适合绝大多数二维 DP 题画表是理解状态转移最直接的方式。3. 代码落地从二维表到一维滚动数组3.1 二维 DP面试最稳妥的版本先把最不容易出错的二维版本写出来。这个版本虽然空间复杂度是 O(m * n)但逻辑一目了然适合作为你思考的主线。public int maximalSquare(char[][] matrix) { if (matrix null || matrix.length 0 || matrix[0].length 0) { return 0; } int m matrix.length; int n matrix[0].length; int[][] dp new int[m][n]; int maxSide 0; for (int i 0; i m; i) { for (int 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(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) 1; } maxSide Math.max(maxSide, dp[i][j]); } // matrix[i][j] 0 时 dp[i][j] 保持默认值 0 } } return maxSide * maxSide; }这里有几个容易忽略的点。第一个判空要分三步先判matrix null再判matrix.length 0最后才能判matrix[0].length 0。如果你上来就写matrix[0].length 0遇到一个空数组会直接抛空指针。第二个maxSide初始化为 0这样矩阵全为 0 时返回 0 是自然正确的。第三个内层循环里matrix[i][j] 0时虽然不更新maxSide但 dp 值要保持 0这一点二维版本天然满足因为数组默认值就是 0。3.2 一维滚动数组把空间从 O(m*n) 压到 O(n)二维版本已经能过题但面试官通常还会问一句“能不能优化空间”。答案是能因为观察递推式可以发现dp[i][j]只依赖三个位置dp[i-1][j]上一行同列、dp[i][j-1]当前行左列、dp[i-1][j-1]上一行左列。也就是说我们根本不需要保留完整的二维表只需要“上一行”的一维值就能推出当前行的所有值。用一个长度为 n 的数组dpdp[j]在更新前保存的是上一行的值更新后保存的是当前行的值。但问题来了dp[i-1][j-1]这个值在更新dp[j]之前已经被当前行的dp[j-1]覆盖了吗不会因为前一个格子(i, j-1)更新的是dp[j-1]不是dp[j]。真正危险的是你在计算dp[j]时需要引用“上一行 j-1 列”的值可dp[j-1]已经变成了当前行的值。所以我们必须用一个额外变量prev在每次更新dp[j]之前先把旧值保存下来。public int maximalSquare(char[][] matrix) { if (matrix null || matrix.length 0 || matrix[0].length 0) { return 0; } int m matrix.length; int n matrix[0].length; int[] dp new int[n]; int maxSide 0; for (int i 0; i m; i) { int prev 0; // 相当于 dp[i][-1] 或者说 dp[i-1][j-1] 的初始值 for (int j 0; j n; j) { int temp dp[j]; // 保存 dp[i-1][j-1] 的旧值当然这里 j0 时是边界 if (matrix[i][j] 1) { if (i 0 || j 0) { dp[j] 1; } else { dp[j] Math.min(Math.min(dp[j], dp[j - 1]), prev) 1; } maxSide Math.max(maxSide, dp[j]); } else { dp[j] 0; // 关键不清零会把上一行的残留值带到当前行 } prev temp; } } return maxSide * maxSide; }我再强调一遍这个prev的时序同行从左到右遍历时dp[j-1]已经是本行新值dp[j]还没有被更新所以还是上一行旧值prev保存的就是更早一步的“本行更新前的 dp[j-1]”也就是上一行 j-1 列的值。每走一格prev就要向前滚动一次。很多同学第一次写滚动数组时把prev temp放在了更新dp[j]之后甚至直接省掉结果一跑测试就错。这个坑属于典型的“看着简单写起来老翻车”。3.3 别的语言注意点与本地方案如果你用 C写法几乎一样但注意vectorvectorchar的比较也是1。如果用 Python矩阵是一个由字符串组成的列表比如[1010, 1011]那matrix[i][j] 1依然成立但要小心 Python 字符串不可变你不能直接改matrix[i][j]。如果一开始读入的是整数矩阵[[1,0,1,0],[1,0,1,1]]那条件就变成 1。我建议在预处理阶段统一转成合适的类型别在核心循环里反复纠结。关于原地修改有人会问能不能直接用原矩阵当 dp 表省掉额外空间。理论可行把非 1 的位置写成 dp 值、把 1 的位置覆盖成更新后的边长就行。但我不推荐在面试里主动用一是可读性差二是如果你后续还需要原矩阵做其他分析数据已经被破坏了。除非面试官明确要求“只能用 O(1) 额外空间”否则用一维滚动数组已经是足够优秀的答案。还有一个小优化遍历的外层选行还是选列会影响滚动数组的长度。如果 m 远小于 n你可以先转置矩阵再按行遍历让滚动数组长度变成 m进一步省空间。这个优化在 LeetCode 上没必要做但提一句可以让面试官觉得你考虑得周全。4. 复杂度分析与正确性验证4.1 时间与空间复杂度拆解先看时间。二维 DP 的每个格子只做常数次比较和一次取最小值所以总时间是 O(m * n)。滚动数组版本的内层循环也完全一样时间依然是 O(m * n)。空间方面二维版 O(m * n)滚动版 O(n)。也就是说滚动数组在不牺牲时间的前提下把空间从平方级别降到了线性级别代价只是多维护一个prev变量。为什么暴力枚举不行如果 m n 1000暴力加前缀和判断是 O(10^9) 量级现代 OJ 基本超时DP 则是 O(10^6)差距非常明显。这个复杂度差距正是面试官希望听到你分析出来的。如果你一上来就暴力写代码在 LeetCode 上大概率会看见超时的红色提示。我还整理了常见解法的对比方便你面试时直接拿来用。解法时间复杂度空间复杂度适用场景备注暴力 前缀和O(m * n * min(m, n))O(m * n)小矩阵调试思路直观适合做对数器二维 DPO(m * n)O(m * n)常规解法最容易讲清楚的版本滚动数组 DPO(m * n)O(n)面试加分需理解 prev 的滚动时机前缀和 二分边长O(m * n * log min(m, n))O(m * n)可做题但常数大验证单调性后可二分不主流单调栈每行直方图O(m * n)O(n)可扩展到 85 题代码长杀鸡用牛刀4.2 正确性论证从两个方向看递推式很多人在代码层面“会用”但正确性说不清楚。前面我已经给过一个双向证明的框架这里再展开讲细一点。先定义dp[i][j]是“以(i,j)为右下角的最大全 1 正方形边长”。如果这个值至少是 x那么意味着以它为右下角确实存在一个边长为 x 的全 1 正方形。现在假设(i,j)这个格子是1并且它左右上三个方向的 dp 值分别是 a、b、c。我们想证明dp[i][j] min(a,b,c) 1是精确的。第一dp[i][j]不可能超过min(a,b,c) 1。因为如果要构造边长 k 的正方形那左上角的那块边长为 k-1 的正方形必须落在dp[i-1][j-1]能覆盖的范围内同时上方和左方也都要有至少 k-1 的高度三者缺一不可。所以 k-1 ≤ a、b、c 都得成立k ≤ min(a,b,c)1。这是上界。第二min(a,b,c) 1一定能达到。设 t min(a,b,c)那么三个方向都能提供边长至少为 t 的全 1 正方形。以(i-1,j)为右下角的 t 正方形覆盖上方以(i,j-1)为右下角的 t 正方形覆盖左方以(i-1,j-1)为右下角的 t 正方形覆盖左上角。把这三个正方形和当前格子(i,j)拼在一起恰好构成一个边长为 t1 的全 1 正方形。这是下界。上下界一夹等号成立。这个证明虽然有点绕但只要你在纸上画一遍就能理解三格 min 不是玄学而是“覆盖关系”的必然结果。面试时能把这个证明讲出来比单纯写出代码的印象分高很多。4.3 边界样例与实际跑测我自己刷题时会给每个 DP 题准备一个小测试集。221 的测试集我会这样设计全 0 矩阵期望 0全 1 的 3x3 矩阵期望 9单行[0,1,1]期望 1单列同样期望 1混合矩阵[10100,10111,11111,10010]这是 LeetCode 官方示例期望 4手动推演混合矩阵时你会发现dp 值最大的地方总是出现在连续 1 区域的右下角。比如第 2 行第 3 列的位置0 基它上方和左上方形成了边长 2 的正方形所以 dp 值变成了 2最终答案是 4。这类样例跑通后再随机生成大矩阵拿暴力和 DP 对拍基本就能确定代码的正确性了。5. 实战中踩过的坑这题的小陷阱比想象中多5.1 空矩阵与判空顺序LeetCode 的判空比较友好但如果你用本地 IDE 或者去一些 ACM 风格的 OJ 刷题输入可能直接给空数组。判空顺序一旦写反就是空指针异常。正确顺序一定是if (matrix null || matrix.length 0 || matrix[0].length 0)这个顺序看起来简单但如果你写matrix[0].length 0在前遇到matrix本身为 null 时根本走不到第二个条件先抛异常了。类似的判空问题在二维数组相关题目里非常常见建议所有矩阵类题目都统一采用这个三段式检查。5.2 单行单列时边界条件不能省当矩阵只有一行或一列时任何dp[i][j]都会命中i 0 || j 0分支。这意味着所有找到的 1 都只能组成边长 1 的正方形最终答案要么是 0 要么是 1。很多人在单行测试用例上出错不是边界条件写错而是在一维滚动数组版本里把prev的管理搞混了。比如 j0 时prev初始值应该是 0因为dp[i-1][-1]根本不存在你不能让prev变成上一行最后一列的值。解决办法是每行开始时重置prev 0并在每个 j 循环开头先保存temp dp[j]。5.3 把边长当面积直接返回这大概是我见过最多的错误。dp[i][j]存的是边长maxSide也是边长最后必须用maxSide * maxSide得到面积再返回。有些同学一直记着题目要返回面积结果在更新maxSide时就不小心写成了Math.max(maxSide, dp[i][j] * dp[i][j])这样虽然逻辑上没错却在每个格子都做了一次乘法反而可能搞混 dp 的含义。我建议动态规划过程中一律只维护边长最后一步统一乘方这样最容易检查。5.4 滚动数组不清零的坑这是滚动数组版本里最隐蔽的错误。二维 DP 中matrix[i][j] 0时 dp 值是 0数组默认就是 0不需要额外操作。但是一维滚动数组里dp[j]在进入新一行时依然保存着上一行的旧值。如果你在matrix[i][j] 0时什么都不做旧值就会残留后续计算 min 时会把上一行的边长错误地借过来导致结果偏大。正确写法是在else分支里显式dp[j] 0。这个 bug 不随机生成大规模数据对拍很难发现因为小矩阵可能碰巧不出错。5.5 char 与 int 的混淆再强调一次1与1的区别在 Java、C 里是引号问题在 Python 里是类型问题。我自己有一段时间从 C 切到 Java经常写matrix[i][j] 1因为脑子里想着整数 1结果所有判断都是 false最后输出恒为 0。排查了一下午才发现是引号问题。从此我养成了一个习惯读题时先圈出矩阵元素类型在代码注释里写上// 注意是字符 1不是 int 1。这个习惯听起来很小但真的能省下大把调试时间。6. 由 221 引出的知识迁移这是整个“全 1 矩阵”家族的入口6.1 最大矩形LeetCode 85什么时候三格 min 不再成立把 221 改成“最大全 1 矩形”就变成了 LeetCode 85。矩形允许宽和高不相等三格 min 的 DP 就不再成立因为你拼出来的必须是一个长宽可能不同的区域不是简单取最短边就能覆盖的。85 的常用解法是把每一行看成直方图的底部统计每个位置向上连续 1 的高度然后用单调栈求出每个高度作为最小高度时能往左右延伸多宽从而算出该行对应的最大矩形面积遍历所有行取最大值。这个过程可以看作是把二维问题降维成一维直方图问题单调栈是核心工具。如果你先做 221 再做 85会发现两者虽然有相似之处但思考方式完全不同。221 的 min 三格是正方形约束带来的“特事特办”85 的单调栈则是一般矩形问题的通用思路。很多面试官喜欢把这两题放在一起考你想展示自己的知识体系可以主动说“221 是正方形的特例85 是不能用三格 min 的通用矩形版本我可以用单调栈解 85。”这个主动迁移非常加分。6.2 统计全 1 正方形子矩阵数量LeetCode 12771277 和 221 几乎共用同一个递推式但目标从“最大边长”变成了“总个数”。定义dp[i][j]依然表示以(i,j)为右下角的最大全 1 正方形边长不过答案不再是maxSide * maxSide而是累加每个dp[i][j]。为什么可以直接累加因为如果以(i,j)为右下角的最大正方形边长是 k那么以它作为右下角的正方形一共有 k 个边长分别是 1, 2, ..., k。把每个位置的 k 加起来就是所有正方形的总数。这道题的神奇之处在于它几乎白送只要你能把 221 的 dp 表画出来1277 就只是把Math.max换成sum dp[i][j]。6.3 面试讲法建议怎么把一道简单题讲出层次感221 在 LeetCode 上标的是中等难度但它的面试定位其实很灵活。我见过不少候选人直接写出最优解结果面试官觉得他是背题追问几句就露馅。更稳妥的讲法是层层递进先说暴力再分析复杂度然后引导到 DP最后补上空间优化。这样做不是拖延时间而是展示一个完整的 problem-solving 过程如何从朴素想法逐步发现更优的结构。具体环节可以这样安排拿到题后说“我先想到枚举左上角和边长配合前缀和做到 O(mnmin(m,n))但这不是最优”。然后写出递推式讲清楚 min 的覆盖关系来源。代码完成后主动说“空间还能优化因为每个状态只依赖上一行可以滚成一维数组”。最后再提一句“如果题目改成最大矩形思路会变成单调栈”。这一套流程走下来面试官基本能确认你不是背题而是真的有分析能力。我自己在模拟面试里指导过很多同学用这个套路通过率明显比只背最优解要高。最后分享一个我个人养成的小习惯做任何二维 DP 题我都会先在草稿纸上填一个 3x3 或 4x4 的 dp 表即便是滚瓜烂熟的题也填一遍。这看起来有点浪费时间但正是这个动作帮我躲过了无数次低级错误。LeetCode 221 这题的公式确实好背但真正把它吃透的标志是你能闭眼画出 min 三格的覆盖关系、能解释滚动数组里 prev 的来龙去脉、能顺手把它迁移到 85 和 1277。达到这个程度再去刷下一题你会明显感到动态规划的题目之间开始“串”起来了。