Python程序：通过列重排查找最大子矩阵面积

假设我们有一个二进制矩阵。我们可以随意多次重新排列列，然后找到并返回仅包含 1 的最大子矩阵的面积。

所以，如果输入类似于

则输出将为 4，因为我们可以将其排列为：

为了解决这个问题，我们将遵循以下步骤：

• n := 矩阵的行数
• m := 矩阵的列数
• ans := 0
• 对于 i 从 1 到 n - 1，执行以下操作：
  • 对于 j 从 0 到 m - 1，执行以下操作：
    • 如果 matrix[i, j] 为 1，则：
      • matrix[i, j] := matrix[i, j] + matrix[i-1, j]
• 对于矩阵中的每一行，执行以下操作：
  • 对该行进行排序
  • 对于 j 从 m-1 到 0，递减 1，执行以下操作：
    • ans := ans 和 row[j] *(m - j) 中的最大值
• 返回 ans

示例

让我们看看下面的实现以更好地理解：

def solve(matrix):
   n, m = len(matrix), len(matrix[0])
   ans = 0
   for i in range(1, n) :
      for j in range(m) :
         if matrix[i][j] :
          matrix[i][j] += matrix[i-1][j]
   for row in matrix :
      row.sort()
      for j in range(m-1, -1, -1):
         ans = max(ans, row[j] *(m - j))
   return ans

matrix = [
[1, 0, 0],
[1, 1, 1],
[1, 0, 1]
]
print(solve(matrix))

输入

[
[1, 0, 0],
[1, 1, 1],
[1, 0, 1]
]

输出

4

Arnab Chakraborty

更新于: 2021年10月19日

254 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始