用 Python 编写通过列重排查找最大子矩阵面积的程序

假设我们有一个二元矩阵。我们可以先根据需要多次重新排列列，然后找到仅包含 1 的最大子矩阵的面积。

因此，如果输入如下

那么输出将是 4，因为我们可以将其排列为 −

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

• n := 矩阵的行数
• m := 矩阵的列数
• ans := 0
• 对于范围从 1 到 n - 1 的 i，执行
  • 对于范围从 0 到 m - 1 的 j，执行
    • 如果 matrix[i, j] 为 1，则
      • matrix[i, j] := matrix[i, j] + matrix[i-1, j]
      • 对于矩阵中的每一行，执行
        • 对行进行排序
        • 对于范围从 m-1 到 0 的 j，减少 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
      

      ---

      相关文章

      • Python 中元组列表到字典的转换
      • Python - 从两个列表中配对，使得成对的元素不相同
      • 使用 Python 和 SQLite 的 SQL
      • 使用 pytrie 模块在 Python 中进行前缀匹配
      • 创建和访问 Python 包
      • 如何使用正则表达式和数据类型选择多个 DataFrame 列
      • 如何在 Pandas 中查找和过滤重复行?
      • 用 Python 编写程序以正确的顺序查找机场?
      • 如何在 Python Pandas 中使用字典顺序切片选择数据子集?
      • 用 Python 编写程序检查我们是否可以从给定的字符串字符中创建 k 个回文?

      ---

      有用资源

      • python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

      ---

      打印 下一节:Python Pandas - 将 DateTimeIndex 转换为 Series ❯❮ 上一节:Python Pandas - 将 DatetimeIndex 返回为 datetime.datetime 对象的对象 ndarray