企业官网建设流程全解析

• 示例工程
• 教程

导读

本篇基于 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.py）：

class 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 1

3.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 格连续黑」的信息。

四、枚举判定：从大到小找边长，第一次命中即答案

预处理完成后，进入枚举阶段。策略是：

1. 边长 k 从大到小枚举（n到1），保证第一次找到的就是最大边长，找到后直接返回，避免继续检查更小的正方形；
2. 左上角 (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 版本完全同构：

以下给出 Java 与 Go 的完整参考实现（其余语言见对应文件）。

Java（Solution.java）：

class 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]; } }

Go（Solution.go）：

func 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 i+1 < n { down[i][j] += down[i+1][j] } if j+1 < n { right[i][j] += right[i][j+1] } } } } 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[i+k-1][j] >= k && down[i][j+k-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{}，均对应题目要求的「空数组」。

六、边界情况与易错点

1. 空矩阵 / 零矩阵：若matrix为空或全为白（1），枚举不会命中任何k，返回空数组即可；全为黑（0）时，第一次枚举k = n、左上角(0, 0)即命中，返回[0, 0, n]。
2. 单点答案：当不存在边长 ≥ 2 的黑边方阵时，任何单个黑色像素(i, j)都满足down[i][j] >= 1、right[i][j] >= 1，最终会退化为返回某个[i, j, 1]——这正是示例 2 输出[0,0,1]的原因（行优先枚举保证取到r、c最小者）。
3. 左上角枚举上界：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]会越界。
4. 预处理顺序不可颠倒：若改为从左上角正序递推，down[i][j]会读到尚未计算的down[i + 1][j]，结果全部为 0，判定随之失效。

七、变体与迁移：1139. 最大的以 1 为边界的正方形

本题在仓库中有直接对应的变体题：1139. 最大的以 1 为边界的正方形（LeetCode 第 147 场周赛 Q3，难度中等）。两者的解法骨架完全一致：

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.*文件。

• 示例工程
• 教程