# 找到 1 的最大矩形，并允許交換列 > 原文： [https://www.geeksforgeeks.org/find-the-largest-rectangle-of-1s-with-swapping-of-columns-allowed/](https://www.geeksforgeeks.org/find-the-largest-rectangle-of-1s-with-swapping-of-columns-allowed/) 給定具有 0 和 1 的矩陣，請找到矩陣中所有 1 的最大矩形。 可以通過交換給定矩陣的任何一對列來形成矩形。 **示例**： ``` Input: bool mat[][] = { {0, 1, 0, 1, 0}, {0, 1, 0, 1, 1}, {1, 1, 0, 1, 0} }; Output: 6 The largest rectangle's area is 6\. The rectangle can be formed by swapping column 2 with 3 The matrix after swapping will be 0 0 1 1 0 0 0 1 1 1 1 0 1 1 0 Input: bool mat[R][C] = { {0, 1, 0, 1, 0}, {0, 1, 1, 1, 1}, {1, 1, 1, 0, 1}, {1, 1, 1, 1, 1} }; Output: 9 ``` 想法是使用輔助矩陣存儲每列中連續 1 的計數。 一旦有了這些計數，便以非遞增的計數順序對輔助矩陣的所有行進行排序。 最后遍歷排序的行以找到最大面積。 注意：形成輔助矩陣后，每一行都變得獨立，因此我們可以獨立地交換或排序每一行。這是因為我們只能交換列，因此我們使每一行獨立，并找到了矩形的最大面積 行和列。 以下是上述第一個示例的詳細步驟。 **步驟 1**：首先，計算編號。 每列中的連續 1 個。 輔助數組 hist [] []用于存儲連續 1 的計數。 因此，對于上述第一個示例，hist [R] [C]的內容為 ``` 0 1 0 1 0 0 2 0 2 1 1 3 0 3 0 ``` 此步驟的時間復雜度為 O（R * C） **步驟 2**：以非遞增方式對列進行排序。 排序步驟后，矩陣 hist [] []將為 ``` 1 1 0 0 0 2 2 1 0 0 3 3 1 0 0 ``` 此步驟可以在 O（R *（R + C））中完成。 因為我們知道值的范圍是 0 到 R，所以我們可以對每一行使用計數排序。 排序實際上是列的交換。 如果我們看步驟 2 的第三行： 3 3 1 0 0 排序的行對應于交換列，以便將具有最高可能矩形的列放在最前面，然后是 第二高的矩形，依此類推。 因此，在該示例中，有 2 列可以形成一個高度 3 的矩形。這使面積為 3 * 2 = 6。 如果我們嘗試使矩形變寬，則高度會降低到 1，因為沒有剩余的列允許在第三行上有更高的矩形。 **步驟 3**：遍歷 hist [] []的每一行并檢查最大面積。 由于每一行都按 1 的計數排序，因此可以通過將列數乘以 hist [i] [j]中的值來計算當前區域。 此步驟還需要 O（R * C）時間。 下面是基于以上思想的實現。 ## C++ ```cpp // C++ program to find the largest rectangle of 1's with swapping // of columns allowed. #include <bits/stdc++.h> #define R 3 #define C 5 using namespace std; // Returns area of the largest rectangle of 1's int maxArea(bool mat[R][C]) { ????// An auxiliary array to store count of consecutive 1's ????// in every column. ????int hist[R + 1][C + 1]; ????// Step 1: Fill the auxiliary array hist[][] ????for (int i = 0; i < C; i++) { ????????// First row in hist[][] is copy of first row in mat[][] ????????hist[0][i] = mat[0][i]; ????????// Fill remaining rows of hist[][] ????????for (int j = 1; j < R; j++) ????????????hist[j][i] = (mat[j][i] == 0) ? 0 : hist[j - 1][i] + 1; ????} ????// Step 2: Sort columns of hist[][] in non-increasing order ????for (int i = 0; i < R; i++) { ????????int count[R + 1] = { 0 }; ????????// counting occurrence ????????for (int j = 0; j < C; j++) ????????????count[hist[i][j]]++; ????????// Traverse the count array from right side ????????int col_no = 0; ????????for (int j = R; j >= 0; j--) { ????????????if (count[j] > 0) { ????????????????for (int k = 0; k < count[j]; k++) { ????????????????????hist[i][col_no] = j; ????????????????????col_no++; ????????????????} ????????????} ????????} ????} ????// Step 3: Traverse the sorted hist[][] to find maximum area ????int curr_area, max_area = 0; ????for (int i = 0; i < R; i++) { ????????for (int j = 0; j < C; j++) { ????????????// Since values are in decreasing order, ????????????// The area ending with cell (i, j) can ????????????// be obtained by multiplying column number ????????????// with value of hist[i][j] ????????????curr_area = (j + 1) * hist[i][j]; ????????????if (curr_area > max_area) ????????????????max_area = curr_area; ????????} ????} ????return max_area; } // Driver program int main() { ????bool mat[R][C] = { { 0, 1, 0, 1, 0 }, ???????????????????????{ 0, 1, 0, 1, 1 }, ???????????????????????{ 1, 1, 0, 1, 0 } }; ????cout << "Area of the largest rectangle is " << maxArea(mat); ????return 0; } ```