本文共 868 字，大约阅读时间需要 2 分钟。

以1为边界的最大正方形与仅包含1的最大正方形

一、以1为边界的最大正方形

动态规划解法

为了找到边界全为1的最大正方形，我们可以使用动态规划的方法。以下是详细的步骤：

1. 预处理阶段

创建一个三维数组 dp[i][j][0] 和 dp[i][j][1]，分别表示网格点 (i,j) 横向和竖向连续的1的个数。

• 遍历网格中的每一个点 (i,j)。
• 如果当前点是0，跳过。
• 如果是1，计算横向和竖向连续的1的个数。
  • dp[i][j][0] = dp[i][j-1][0] + 1
  • dp[i][j][1] = dp[i-1][j][1] + 1

2. 寻找最大边长

遍历网格中的每一个点 (i,j)，以该点为右下角的正方形的边长为 curSide = min(dp[i][j][0], dp[i][j][1])。

• 如果 curSide 小于当前最大边长 maxSide，无需继续。
• 否则，检查左边和上边是否可以支持这个边长的正方形。
  • 缩小边长 curSide，直到找到满足条件的最大边长。

3. 复杂度分析

• 时间复杂度：O(m×n×min(m,n))
• 空间复杂度：O(m×n)

二、仅包含1的最大正方形

动态规划解法

为了找到仅包含1的最大正方形，同样可以使用动态规划的方法：

1. 预处理阶段

创建一个二维数组 dp，其中 dp[i][j] 表示以 (i,j) 为右下角的最大正方形的边长。

• 遍历网格中的每一个点 (i,j)。
• 如果当前点是1，计算 dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1。
• 否则，dp[i][j] = 0。

2. 寻找最大边长

遍历 dp 数组，找到最大的值 maxSide，然后计算其平方作为结果。

3. 复杂度分析

• 时间复杂度：O(m×n)
• 空间复杂度：O(m×n)

总结

通过动态规划，我们可以高效地解决这两个问题，避免了暴力枚举的高时间复杂度。每个问题都通过预处理和状态转移，有效地降低了时间和空间复杂度，使得问题在合理的时间内得以解决。

转载地址：http://zlhfk.baihongyu.com/