LeetCode 面试题 17.23. 最大黑方阵

约 6 分钟
文章信息 3 个分类 3 个标签
分类
LeetCode 中等 程序员面试金典（第 6 版）
标签
数组 动态规划 矩阵

题目描述

✅ 面试题 17.23. 最大黑方阵

image-20260929010613608

题意分析

方阵中 0 是黑色、1 是白色，寻找四条边全部为黑色的最大正方形，内部颜色不受限制。返回左上角行、列和边长；同边长时行号更小优先，再选列号更小者，没有黑色边框则返回空数组。

解法：预处理连续黑格 + 枚举边长

核心思路

[!blue]

枚举一个左上角与边长后，直接扫描四条边会反复检查相同黑格。可以预先记录连续长度，将整个边框的验证压缩成四次数组查询。

定义 right[row][col] 为从当前格向右连续黑格的数量，down[row][col] 为向下连续黑格的数量，两者都包含当前格。白格的两个值为零；黑格则在右侧或下侧已有的连续长度上加一。因为依赖右邻与下邻，按行、列都从大到小扫描，使用依赖时它们已经算好。边界没有邻格时只计当前黑格的一。

对左上角 (row, col)、边长 size，右边界为 rightCol = col + size - 1，下边界为 bottom = row + size - 1。上边与左边分别要求 right[row][col] >= size、down[row][col] >= size；下边从 (bottom, col) 向右检查，右边从 (row, rightCol) 向下检查，也都要求连续长度至少为 size。

四个条件正好覆盖四条边：每个计数足够长，意味着该条边没有白格；四条都通过，整个边框就合法。大于边长的计数同样可以接受，边框之外是否继续为黑色没有影响，内部格子也无需检查。

边长从 n 递减枚举，第一次命中的尺寸必然最大。固定尺寸时，左上角先按行升序、再按列升序遍历，所以第一次命中也满足并列时的坐标要求，可以直接返回。一直检查到边长一仍无解，说明没有可用黑格，返回空数组。

解题步骤

  1. 创建两张连续黑格表，从右下向左上计算向右、向下的连续长度。
  2. 边长从大到小枚举，遍历能容纳该尺寸的左上角，即 row + size <= n、col + size <= n。
  3. 用左上、左下、右上三个角上的四个计数检查全部边框。
  4. 首次通过立即返回位置和边长；全部失败则返回空数组。

代码实现

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(n^2)$，用于向右和向下的两张计数表。

关键点总结

[!green]

  • 只判断边框，四个连续长度已足够，不必检查内部面积。
  • 逆序填表与向右、向下的依赖一致，保证连续长度可以直接递推。
  • 大尺寸优先、行优先、列次之的遍历顺序，同时处理最大面积和坐标并列规则。

易错点总结

[!yellow]

  • 黑色对应零，不能按常见的“一代表目标色”写反条件。
  • 下边要从左下角向右查，右边要从右上角向下查，不能重复检查左上角的两条边。
  • 右下边界坐标是起点加 size - 1，使用 size 会越过候选方阵。
  • 边长从小到大首次返回只会得到较小解；同尺寸先枚举列也可能违反最小行号要求。

相似题目

题目 难度 关联与区别
1139. 最大的以 1 为边界的正方形 中等 同样只要求正方形边框满足条件，原题1为目标色并返回面积，本题0为黑色且返回位置和边长。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/77907531
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！