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


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

所以,如果输入类似于

100
111
101

则输出将为 4,因为我们可以将其排列为:

100
111
110

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

  • 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

示例

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

Open Compiler
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]
]

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

4

更新于: 2021年10月19日

254 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告