LeetCode 面试题 17.23. 最大黑方阵
目录
题目描述
题意分析
方阵中 0 是黑色、1 是白色，要找边框全部为黑色的最大正方形，返回
[row,col,size]。内部可以包含白格；若同尺寸有多个答案，行号更小优先，再比较列号。枚举左上角与边长后逐格扫描四条边，一次验证要
O(size)，总复杂度达到O(n^4)。验证重复访问的正是“从某格向右/向下连续有多少黑格”，可以预处理后用四次数组查询判断一条边框。只需要 right 和 down 两张表：上、下边用 right，左、右边用 down。
解法：预处理连续黑格 + 枚举边长
核心思路
right[r][c]表示从(r,c)向右连续 0 的数量，down[r][c]表示向下连续 0 的数量。因为状态依赖右侧和下侧，所以必须从右下向左上填表。对左上角
(r,c)、边长 size，令bottom=r+size-1、rightCol=c+size-1。边框合法当且仅当：
right[r][c] >= size（上边）；down[r][c] >= size（左边）；right[bottom][c] >= size（下边）；down[r][rightCol] >= size（右边）。从 size=n 递减枚举，第一次找到的就是最大尺寸；同一尺寸内 row、col 升序枚举，第一次也满足最小坐标规则。
例：
matrix=[[0,0,0],[0,1,0],[0,0,0]]。四条长度 3 的边全黑，中心是白色并不影响答案，四次查询均至少为 3，直接返回[0,0,3]。
解题步骤
- 创建 n×n 的 right、down 数组。
- 从 row=n-1、col=n-1 逆序扫描；当前格为 0 时，在右/下邻居计数基础上加一。
- 边长从 n 递减到 1。
- 对每个能容纳该边长的左上角，计算 bottom 与 rightCol。
- 用四个连续长度判断边框；命中立即返回。
- 所有候选失败则返回空数组。
代码实现
class Solution {
public int[] findSquare(int[][] matrix) {
int n = matrix.length;
int[][] right = new int[n][n];
int[][] down = new int[n][n];
for (int row = n - 1; row >= 0; row--) {
for (int col = n - 1; col >= 0; col--) {
if (matrix[row][col] == 0) {
right[row][col] = 1;
down[row][col] = 1;
if (col + 1 < n) {
right[row][col] += right[row][col + 1];
}
if (row + 1 < n) {
down[row][col] += down[row + 1][col];
}
}
}
}
for (int size = n; size >= 1; size--) {
for (int row = 0; row + size <= n; row++) {
for (int col = 0; col + size <= n; col++) {
int bottom = row + size - 1;
int rightCol = col + size - 1;
if (right[row][col] >= size
&& down[row][col] >= size
&& right[bottom][col] >= size
&& down[row][rightCol] >= size) {
return new int[] {row, col, size};
}
}
}
}
return new int[0];
}
}
func findSquare(matrix [][]int) []int {
n := len(matrix)
right := make([][]int, n)
down := make([][]int, n)
for row := 0; row < n; row++ {
right[row] = make([]int, n)
down[row] = make([]int, n)
}
for row := n - 1; row >= 0; row-- {
for col := n - 1; col >= 0; col-- {
if matrix[row][col] == 0 {
right[row][col] = 1
down[row][col] = 1
if col+1 < n {
right[row][col] += right[row][col+1]
}
if row+1 < n {
down[row][col] += down[row+1][col]
}
}
}
}
for size := n; size >= 1; size-- {
for row := 0; row+size <= n; row++ {
for col := 0; col+size <= n; col++ {
bottom := row + size - 1
rightCol := col + size - 1
if right[row][col] >= size &&
down[row][col] >= size &&
right[bottom][col] >= size &&
down[row][rightCol] >= size {
return []int{row, col, size}
}
}
}
}
return []int{}
}
复杂度分析
- 时间复杂度：
O(n^3)。预处理O(n^2)；n 种边长，每种最多枚举O(n^2)个左上角，每个候选O(1)验证。- 空间复杂度：
O(n^2)，两张连续黑格计数表。
关键点总结
- 题目只要求边框黑，内部状态完全无关。
- 预处理方向必须与依赖方向相反：向右、向下计数要从右下往左上。
- 四条边分别对应两个 right 查询和两个 down 查询。
- 面试追问能否降空间：可以把每格的 right/down 打包存储，但数量级仍为
O(n^2)；若改成前缀和也能O(1)查边，仍需O(n^2)预处理。
易错点总结
- 把整个正方形都要求为 0：示例中心为 1 仍应返回
[0,0,3]，检查面积会错误拒绝。- 从左上向右下计算 right/down：依赖的右格、下格尚未得到，连续长度全错。
- 下边仍查
right[r][c]：同一条上边被检查两次，底边白色也可能误判合法；应查right[bottom][c]。- 右边从右下角向下查：会越界或检查错段；右边起点是
(r,rightCol)。- 边长从小到大并首次命中就返回：会返回 1×1，而不是最大方阵。
- 同尺寸先枚举列再枚举行：并列时可能不满足题目要求的最小行号。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 221. 最大正方形 | 中等 | 要求内部全为 1 的二维 DP |
| 85. 最大矩形 | 困难 | 全 1 矩形与单调栈 |
| 1277. 统计全为 1 的正方形子矩阵 | 中等 | 正方形 DP 计数 |