在二进制矩阵中寻找最大全1正方形

最后修改:2024年3月18日

by Said Sryheni

1. 概述

在本教程中，我们将讨论如何在一个仅由0和1组成的二进制矩阵中，找出由1组成的最大正方形子矩阵。

我们会先定义问题，然后通过一个示例来解释它。接着，我们介绍四种不同的解法，并分析它们的时间复杂度。

2. 问题定义

我们被给定一个大小为 N × M 的二进制矩阵，每个单元格的值为0或1。我们的任务是找出由1组成的最大正方形子矩阵的边长。

来看一个示例：

FullOnes 1

图中，最大全1正方形子矩阵的左上角坐标为 (2, 2)，右下角坐标为 (4, 4)，边长为3。

3. 暴力法

3.1 思路

暴力法的核心思想是：遍历所有可能的左上角作为正方形的起点，然后枚举每一个可能的边长，判断该正方形是否全由1组成。

3.2 判断子矩阵是否全为1

boolean isFull(int[][] matrix, int x1, int y1, int x2, int y2) {
    for (int i = x1; i <= x2; i++) {
        for (int j = y1; j <= y2; j++) {
            if (matrix[i][j] == 0) {
                return false;
            }
        }
    }
    return true;
}

3.3 算法实现

int maxSquareBruteForce(int[][] matrix) {
    int n = matrix.length;
    int m = matrix[0].length;
    int maxLen = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int len = 1; i + len <= n && j + len <= m; len++) {
                if (isFull(matrix, i, j, i + len - 1, j + len - 1)) {
                    maxLen = Math.max(maxLen, len);
                }
            }
        }
    }

    return maxLen;
}

3.4 时间复杂度

  • 时间复杂度：O(N² × M² × L)，其中 N 是行数，M 是列数，L 是最大可能的正方形边长（即 min(N, M)）
  • 说明：对每个可能的左上角 (i, j)，我们尝试所有可能的边长，并对每个边长遍历整个子矩阵进行判断

✅ 优点：思路简单，容易实现
❌ 缺点：效率极低，只能处理非常小规模的数据

4. 前缀和优化（动态规划）

4.1 思路

我们使用二维前缀和技巧来优化 isFull() 函数，使其能在 O(1) 时间内判断一个子矩阵是否全为1。

我们构建一个前缀和数组 prefix[i][j]，表示从 (0, 0) 到 (i, j) 的子矩阵中所有元素的和。

构建公式如下：

prefix[i][j] = matrix[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]

要判断一个子矩阵是否全为1，我们只需计算它的面积和对应的前缀和：

area = (x2 - x1 + 1) * (y2 - y1 + 1)
sum = prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]
return sum == area;

4.2 算法实现

int maxSquareDP(int[][] matrix) {
    int n = matrix.length;
    int m = matrix[0].length;
    int[][] prefix = new int[n + 1][m + 1];

    // Build prefix sum
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            prefix[i][j] = matrix[i - 1][j - 1] +
                           prefix[i - 1][j] +
                           prefix[i][j - 1] -
                           prefix[i - 1][j - 1];
        }
    }

    int maxLen = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int len = 1; i + len <= n + 1 && j + len <= m + 1; len++) {
                int x1 = i, y1 = j;
                int x2 = i + len - 1, y2 = j + len - 1;

                int area = len * len;
                int sum = prefix[x2][y2] 
                        - prefix[x1 - 1][y2] 
                        - prefix[x2][y1 - 1] 
                        + prefix[x1 - 1][y1 - 1];

                if (sum == area) {
                    maxLen = Math.max(maxLen, len);
                }
            }
        }
    }

    return maxLen;
}

4.3 时间复杂度

  • 时间复杂度：O(N × M × L)
  • 说明：虽然还是三重循环，但每次判断子矩阵是否全为1的时间降为 O(1)

✅ 优点：比暴力法快很多
❌ 缺点：仍不是最优解，复杂度仍较高

5. 二分查找法

5.1 思路

对于每个左上角，我们可以使用二分查找来快速确定以它为起点的最大正方形边长。

利用如下性质：

  • 如果存在边长为 L 的全1正方形，那么所有边长小于 L 的正方形也一定存在
  • 如果不存在边长为 L 的正方形，那么边长更大的也不可能存在

5.2 算法实现

int maxSquareBinarySearch(int[][] matrix) {
    int n = matrix.length;
    int m = matrix[0].length;
    int[][] prefix = new int[n + 1][m + 1];

    // Build prefix sum
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            prefix[i][j] = matrix[i - 1][j - 1] +
                           prefix[i - 1][j] +
                           prefix[i][j - 1] -
                           prefix[i - 1][j - 1];
        }
    }

    int maxLen = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int low = 1;
            int high = Math.min(n - i + 1, m - j + 1);

            while (low <= high) {
                int mid = (low + high) / 2;
                int x2 = i + mid - 1;
                int y2 = j + mid - 1;

                int area = mid * mid;
                int sum = prefix[x2][y2] 
                        - prefix[i - 1][y2] 
                        - prefix[x2][j - 1] 
                        + prefix[i - 1][j - 1];

                if (sum == area) {
                    maxLen = Math.max(maxLen, mid);
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }
    }

    return maxLen;
}

5.3 时间复杂度

  • 时间复杂度：O(N × M × log L)
  • 说明：对每个左上角，我们用二分查找代替了线性查找，复杂度从 O(L) 降到 O(log L)

✅ 优点：比前两种方法快很多
❌ 缺点：实现稍复杂

6. 双指针法（滑动窗口）

6.1 思路

我们维护一个全局变量 len，表示当前找到的最大正方形边长。从左上到右下遍历每个点作为起点，尝试扩展当前的 len。

如果当前边长为 len 的正方形全为1，则尝试扩展为 len+1，否则跳过。

6.2 算法实现

int maxSquareTwoPointers(int[][] matrix) {
    int n = matrix.length;
    int m = matrix[0].length;
    int len = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            while (i + len < n && j + len < m) {
                boolean valid = true;
                for (int k = 0; k <= len; k++) {
                    if (matrix[i + len][j + k] == 0 || matrix[i + k][j + len] == 0) {
                        valid = false;
                        break;
                    }
                }
                if (valid) {
                    len++;
                } else {
                    break;
                }
            }
        }
    }

    return len;
}

6.3 时间复杂度

  • 时间复杂度：O(N × M + L)
  • 说明：每个点最多被检查一次，且 len 不会回退，所以整体复杂度接近线性

✅ 优点：时间复杂度最低，适合大规模数据
⚠️ 注意：实现细节容易出错，比如边界条件的处理

7. 总结

方法 时间复杂度 适用场景
暴力法 O(N² × M² × L) 数据量极小
前缀和优化 O(N × M × L) 中小规模数据
二分查找 O(N × M × log L) 中大规模数据
双指针法 O(N × M + L) 大规模数据
  • ✅ 推荐使用 双指针法 或 二分查找法，它们在时间和实现复杂度之间取得了较好的平衡
  • ⚠️ 如果数据量非常小，可以用暴力法，但要避免在实际项目中使用
  • ✅ 前缀和优化是通用技巧，建议掌握，适用于很多子矩阵/子数组相关问题

原始标题:Finding Maximum Size Square in a Matrix Filled With Ones

« 上一篇： Sockets：Close 与 Shutdown 的区别
» 下一篇： 编译时 vs. 运行时