Java 中的最大正方形矩阵问题

最大的正方形矩阵问题 涉及在一个给定的二进制矩阵中找到最大的正方形子矩阵，其中子矩阵的所有元素都为 1。这是一个经典的动态规划问题，用于高效地解决二维问题。

在 Java 中，解决该问题可以通过创建一个辅助矩阵来存储中间结果，与朴素解法相比，这可以显著降低时间复杂度。

问题陈述

给定一个由 0 和 1 组成的布尔矩阵，找出并打印最大的全为 1 的正方形子矩阵。

最大正方形矩阵示例

矩阵

0 0 1 1

0 1 1 1

0 0 0 1

输出

1 1

1 1

问题解决方案

朴素方法

这是查找最大正方形矩阵的最简单方法。给定问题的算法如下。

算法

步骤 1：创建一个与输入矩阵相同维度的二维辅助矩阵 S，用于存储以每个位置为终点的最大正方形子矩阵的大小。

步骤 2：将输入矩阵的第一行和第一列直接复制到辅助矩阵 S 中。跟踪在这些行和列中找到的最大正方形子矩阵的大小。

步骤 3：对于输入矩阵中的每个单元格 matrix[i][j]（从第二行和第二列开始），如果该单元格包含 1，则使用以下公式计算以该单元格为终点的最大正方形子矩阵的大小：

• 如果单元格包含 0，则将 S[i][j] 设置为 0。
• 更新找到的最大正方形子矩阵的尺寸和右下角的位置。

步骤 4：使用跟踪到的最大尺寸和位置打印最大的正方形子矩阵的元素。

步骤 5：返回全为 1 的最大正方形子矩阵的大小。

文件名：LargestSquareMatrix.java

输出

 
The largest square sub-matrix with all 1s is:
1 1 
1 1 
The size of the largest square sub-matrix with all 1s is: 2   

时间复杂度

上述代码的时间复杂度为 O(rows×cols)，其中 rows 是矩阵的行数，cols 是矩阵的列数。这是因为代码会遍历矩阵中的每个单元格一次。

辅助空间

上述代码的辅助空间为 O(rows×cols)。这是因为使用了额外的 S 矩阵空间，其尺寸与输入矩阵相同。

使用动态规划方法

我们将使用一个动态规划 (DP) 表，其中 dp[i][j] 表示以 (i, j) 为右下角的最大的全为 1 的正方形子矩阵的边长。

算法

步骤 1：创建一个与输入矩阵相同维度的二维数组 dp。

步骤 2：如果原始矩阵中的元素为 0，则 DP 表中对应的元素也将为 0，因为任何正方形子矩阵都不能以值为 0 的单元格结束。

步骤 3：如果原始矩阵中的元素为 1，则 dp[i][j] 的值将是其上方 (dp[i-1][j])、左方 (dp[i][j-1]) 和左上方对角线 (dp[i-1][j-1]) 邻居值的最小值加 1。

步骤 4：这将是最大的全为 1 的正方形子矩阵的大小。

让我们在 Java 程序中实现上述算法。

文件名：LargestSquareMatrixDP.java

输出

 
The size of the largest square sub-matrix with all 1s is: 2   

时间复杂度

上述代码的时间复杂度为 O(rows×cols)，其中 rows 是矩阵的行数，cols 是矩阵的列数。这是因为我们遍历了矩阵中的每个单元格一次。

辅助空间

上述代码的辅助空间为 O(rows×cols)。这是因为使用了额外的 dp 数组空间，其尺寸与输入矩阵相同。