示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载导读本篇基于 doocs/leetcode 仓库中《程序员面试金典第 6 版》系列的 17.23.Max Black Square 题解深入剖析「最大黑方阵」这一经典矩阵问题的完整解法先通过自右下角的逆序递推预处理出每个格子向下、向右连续黑色像素的长度down与right再由大到小枚举边长、由小到大枚举左上角以 O(1) 的四角判定找出最大黑边方阵。读完本文你将掌握这一套「预处理 枚举」的通用模板可迁移到 1139 题「最大的以 1 为边界的正方形」并拿到 Python3、Java、C、Go、TypeScript、Swift 六种语言的完整可运行实现。一、题目背景与语义该题出自《程序员面试金典第 6 版》第 17 章是 LCCI 系列中典型的「矩阵 动态规划」问题在仓库 lcci/README.md 中被标注为难度「中等」、标签「动态规划」。题目描述给定一个方阵其中每个单元像素非黑即白。0 代表黑色像素1 代表白色像素。要求设计算法找出4 条边皆为黑色像素的最大子方阵返回一个数组[r, c, size]r、c分别代表子方阵左上角的行号、列号size是子方阵的边长若有多个满足条件的子方阵返回r最小的若r相同返回c最小的若不存在满足条件的子方阵返回空数组。注意「边皆为黑」与「整个区域皆为黑」是两回事本题只要求四条边框线上的像素全为黑色方阵内部可以有白色像素。示例 1输入: [ [1,0,1], [0,0,1], [0,0,1] ] 输出: [1,0,2] 解释: 输入中 0 代表黑色1 代表白色标粗的元素即为满足条件的最大子方阵以左上角(1, 0)、边长2的子方阵为例其四条边为上边(1,0)-(1,1)、下边(2,0)-(2,1)、左边(1,0)-(2,0)、右边(1,1)-(2,1)全部为黑色因此答案为[1,0,2]。示例 2输入: [ [0,1,1], [1,0,1], [1,1,0] ] 输出: [0,0,1]主对角线上的三个黑点互不相连只有单个黑色像素(0,0)能构成边长为 1 的黑边方阵故返回[0,0,1]。提示matrix.length matrix[0].length 200即方阵最大边长 200数据规模决定了我们需要一个优于暴力枚举的算法。二、朴素思路与优化动机先看最直观的暴力做法枚举所有可能的左上角(i, j)与边长k再逐边扫描四条边框上的像素是否全黑。左上角有 O(n²) 种选择边长有 O(n) 种选择每条边最多需要检查 O(n) 个像素。因此朴素枚举的复杂度高达 O(n⁴)在 n 200 的规模下显然不可接受。优化思路文档中的核心思考如果预先知道每个格子向下、向右连续黑色像素的长度那么判定「边长为 k 的正方形四边全黑」就不再需要逐像素扫描——四条边分别可以压缩为四个角的四段连续信息从而把单次判定降到 O(1)整体复杂度降为 O(n³)。三、预处理从右下角逆序递推 down 与 right定义两个与输入同尺寸的二维数组down[i][j]从(i, j)出发向下连续黑色像素值为 0的个数right[i][j]从(i, j)出发向右连续黑色像素值为 0的个数。递推公式如下原文公式完整保留$$ down[i][j] \begin{cases} down[i 1][j] 1, matrix[i][j] 0 \textit{ 且 } i 1 n \ 1, matrix[i][j] 0 \textit{ 且 } i 1 n \ 0, matrix[i][j] 1 \end{cases} $$$$ right[i][j] \begin{cases} right[i][j 1] 1, matrix[i][j] 0 \textit{ 且 } j 1 n \ 1, matrix[i][j] 0 \textit{ 且 } j 1 n \ 0, matrix[i][j] 1 \end{cases} $$关键点遍历顺序必须是从右下角向左上角逆序。因为down[i][j]依赖下方邻居down[i 1][j]right[i][j]依赖右方邻居right[i][j 1]只有逆序枚举i和j才能在计算当前格时保证其依赖项已经就绪。以 Python 实现为例仓库 Solution.pyclass Solution: def findSquare(self, matrix: List[List[int]]) - List[int]: n len(matrix) down [[0] * n for _ in range(n)] right [[0] * n for _ in range(n)] for i in range(n - 1, -1, -1): for j in range(n - 1, -1, -1): if matrix[i][j] 0: down[i][j] down[i 1][j] 1 if i 1 n else 1 right[i][j] right[i][j 1] 1 if j 1 n else 13.1 手工推演一个 3×3 小例子以示例 1 的矩阵为例[1,0,1] [0,0,1] [0,0,1]右下角(2, 2)是白格down[2][2] right[2][2] 0(2, 1)是黑格且处于末行、末列down[2][1] 1、right[2][1] 1(2, 0)同理得down 1、right 1。往上到(1, 1)黑格down[1][1] down[2][1] 1 2、right[1][1] right[1][2] 1 1。依此类推最终down[1][0] 2、right[1][0] 2这正是后续判定边长 2 的黑边方阵所需的「从左上角 (1,0) 向下向右至少 2 格连续黑」的信息。四、枚举判定从大到小找边长第一次命中即答案预处理完成后进入枚举阶段。策略是边长 k 从大到小枚举n到1保证第一次找到的就是最大边长找到后直接返回避免继续检查更小的正方形左上角 (i, j) 从小到大枚举行优先天然满足题目「r 最小、其次 c 最小」的返回要求——注意当k固定时先命中的左上角就是字典序最小的那个。左上角(i, j)的可取值范围0 i n - k、0 j n - k保证子方阵不越界。对于一个候选子方阵左上角(i, j)边长k其四条边全黑的充要条件是四个角上的连续黑段长度都不小于 k左上角(i, j)向下连续黑长度down[i][j] k覆盖左边框左上角(i, j)向右连续黑长度right[i][j] k覆盖上边框左下角(i k - 1, j)向右连续黑长度right[i k - 1][j] k覆盖下边框右上角(i, j k - 1)向下连续黑长度down[i][j k - 1] k覆盖右边框。即文档中的完整判定条件down[i][j] k 且 right[i][j] k 且 right[i k - 1][j] k 且 down[i][j k - 1] k满足则直接返回[i, j, k]全部枚举完仍无命中返回空数组。为什么四个条件充分因为正方形四条边上的像素数量都是 k 个左边框的 k 个像素恰好是(i, j)向下的 k 格右边框的 k 个像素恰好是(i, j k - 1)向下的 k 格上边框与下边框同理。只要相应起点处的连续黑段长度 ≥ k该条边上的 k 个像素必然全部为黑四条边同时满足即构成完整的黑边正方形且方阵内部是否全黑并不影响本题结论。枚举部分的 Python 实现for k in range(n, 0, -1): for i in range(n - k 1): for j in range(n - k 1): if ( down[i][j] k and right[i][j] k and right[i k - 1][j] k and down[i][j k - 1] k ): return [i, j, k] return []复杂度分析预处理阶段遍历一遍矩阵为 O(n²)枚举阶段边长 k 有 O(n) 种取值每种取值下左上角有 O(n²) 个候选总枚举量为 O(n³)实际为 n、n-1、…、1 的平方和即 O(n³)每次判定 O(1)。因此时间复杂度O(n³)空间复杂度O(n²)down与right两个辅助二维数组。五、多语言实现仓库内的六套同构代码同一套算法在仓库中提供了 6 种语言的完整实现均可直接运行逻辑与 Python 版本完全同构语言仓库文件实现要点JavaSolution.java三元表达式i 1 n ? down[i 1][j] 1 : 1完成递推无结果返回new int[0]CSolution.cpp使用定长二维数组int down[n][n]配合memset清零无结果返回{}GoSolution.go用make初始化切片先置 1 再累加down[i1][j]、right[i][j1]TypeScriptSolution.tsArray.from({ length: n }, () Array(n).fill(0))创建二维数组number[]返回类型SwiftSolution.swiftstride(from:through:by:)实现逆序与降序遍历0...(n - k)闭区间枚举左上角Python3Solution.py全文核心版本见上文以下给出 Java 与 Go 的完整参考实现其余语言见对应文件。JavaSolution.javaclass Solution { public int[] findSquare(int[][] matrix) { int n matrix.length; int[][] down new int[n][n]; int[][] right new int[n][n]; for (int i n - 1; i 0; --i) { for (int j n - 1; j 0; --j) { if (matrix[i][j] 0) { down[i][j] i 1 n ? down[i 1][j] 1 : 1; right[i][j] j 1 n ? right[i][j 1] 1 : 1; } } } for (int k n; k 0; --k) { for (int i 0; i n - k; i) { for (int j 0; j n - k; j) { if (down[i][j] k right[i][j] k right[i k - 1][j] k down[i][j k - 1] k) { return new int[] {i, j, k}; } } } } return new int[0]; } }GoSolution.gofunc findSquare(matrix [][]int) []int { n : len(matrix) down : make([][]int, n) right : make([][]int, n) for i : range down { down[i] make([]int, n) right[i] make([]int, n) } for i : n - 1; i 0; i-- { for j : n - 1; j 0; j-- { if matrix[i][j] 0 { down[i][j], right[i][j] 1, 1 if i1 n { down[i][j] down[i1][j] } if j1 n { right[i][j] right[i][j1] } } } } for k : n; k 0; k-- { for i : 0; i n-k; i { for j : 0; j n-k; j { if down[i][j] k right[i][j] k right[ik-1][j] k down[i][jk-1] k { return []int{i, j, k} } } } } return []int{} }各语言实现之间的细微差异值得注意边界处理Python/Java/C/TypeScript/Swift 采用「先判越界再决定取 1 还是取邻居 1」Go 采用「先置 1再在未越界时累加」的等价写法两者语义一致无答案时的返回Java 返回new int[0]Python/TS/Swift 返回[]C 返回{}Go 返回[]int{}均对应题目要求的「空数组」。六、边界情况与易错点空矩阵 / 零矩阵若matrix为空或全为白1枚举不会命中任何k返回空数组即可全为黑0时第一次枚举k n、左上角(0, 0)即命中返回[0, 0, n]。单点答案当不存在边长 ≥ 2 的黑边方阵时任何单个黑色像素(i, j)都满足down[i][j] 1、right[i][j] 1最终会退化为返回某个[i, j, 1]——这正是示例 2 输出[0,0,1]的原因行优先枚举保证取到r、c最小者。左上角枚举上界i、j必须满足i k - 1 n、j k - 1 n即i n - k、j n - k否则访问right[i k - 1][j]、down[i][j k - 1]会越界。预处理顺序不可颠倒若改为从左上角正序递推down[i][j]会读到尚未计算的down[i 1][j]结果全部为 0判定随之失效。七、变体与迁移1139. 最大的以 1 为边界的正方形本题在仓库中有直接对应的变体题1139. 最大的以 1 为边界的正方形LeetCode 第 147 场周赛 Q3难度中等。两者的解法骨架完全一致对比维度面试题 17.23本文1139 题黑/白定义0 为黑1 为白1 为目标色目标最大黑边方阵的[r, c, size]最大 1 边方阵的面积返回k * k预处理down、right记录连续 0 的长度down、right记录连续 1 的长度判定条件四角连续段 k与本文完全相同复杂度O(n³) / O(n²)O(m × n × min(m, n)) / O(m × n)1139 题允许矩阵非方阵m × n枚举边长时上界取min(m, n)判定命中后直接返回k * k而非坐标数组其余递推公式、逆序遍历顺序、四角判定条件均与本文一致。掌握了本文的「预处理 枚举」模板两道题可以一并拿下。八、小结「最大黑方阵」是一道典型的用空间换时间的矩阵 DP 问题直接扫描四边的暴力做法是 O(n⁴)而通过down、right两张表把「边是否够长」压缩为 O(1) 的四角判定配合「边长从大到小、左上角从小到大」的双重枚举顺序一举将复杂度降为 O(n³)同时天然满足题目对[r, c, size]字典序最小的返回要求。其核心要点可归纳为三点右下角逆序递推保证预处理依赖就绪、四角连续段判定替代逐边扫描、第一次命中即返回保证结果最大且有序。完整多语言实现可参阅仓库 lcci/17.23.Max Black Square 目录下的各Solution.*文件。赞分享示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐LeetCode 面试题 17.23 最大黑方阵题解从暴力枚举到记忆化动态规划附 Java/Python 实现LeetCode 面试题 17.23 最大黑方阵题解从暴力枚举到记忆化动态规划附 Java/Python 实现 本题出自《程序员面试金典》面试题 17.2文档教程知识库doocs/leetcode面试题 16.11「跳水板」的分类讨论解法与 O(k) 枚举实现详解doocs/leetcode面试题 16.11「跳水板」的分类讨论解法与 O k 枚举实现详解 本篇围绕 doocs/leetcode 仓库中《程序员面试金典示例工程教程doocs/leetcode 幂集问题全解面试题 08.04 的递归枚举与二进制枚举两种实现doocs/leetcode 幂集问题全解面试题 08.04 的递归枚举与二进制枚举两种实现 本篇技术指南以 doocs/leetcode 仓库中《程序员面试示例工程教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考