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

示例

讓我們看看下面的實現以更好地理解：

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

更新於: 2021年10月19日

254 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告