给定一个包含0和1的矩阵，找出矩阵中所有1的最大矩形。矩形可以通过交换给定矩阵的任意一对列来形成。 例子：
null
Input: bool mat[][] = { {0, 1, 0, 1, 0}, {0, 1, 0, 1, 1}, {1, 1, 0, 1, 0} };Output: 6The largest rectangle's area is 6. The rectangle can be formed by swapping column 2 with 3The matrix after swapping will be 0 0 1 1 0 0 0 1 1 1 1 0 1 1 0Input: 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的数量。辅助数组hist[][]用于存储连续1的计数。因此，对于上面的第一个示例，hist[R][C]的内容将是
0 1 0 1 0 0 2 0 2 1 1 3 0 3 0
该步骤的时间复杂度为O（R*C） 第二步： 以非递增方式对行进行排序。在排序步骤之后，矩阵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 3 1 0 0 排序的行对应于交换列，以便将可能具有最高矩形的列放在第一位，然后是允许第二高矩形的列，依此类推。因此，在这个例子中，有两列可以形成一个高度为3的矩形。这使得面积为3*2=6。如果我们试着让矩形变宽，高度会下降到1，因为第三行没有允许更高矩形的列了。 第三步： 遍历hist[]的每一行，并检查最大面积。由于每一行都是按1的计数排序的，所以可以通过将列数乘以hist[i][j]中的值来计算当前区域。这一步也需要O（R*C）时间。 下面是基于上述想法的实现。
C++
// 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; } |
JAVA
// Java program to find the largest rectangle of // 1's with swapping of columns allowed. class GFG { static final int R = 3 ; static final int C = 5 ; // Returns area of the largest rectangle of 1's static int maxArea( int mat[][]) { // An auxiliary array to store count of consecutive 1's // in every column. int hist[][] = new int [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 rows of hist[][] in non-increasing order for ( int i = 0 ; i < R; i++) { int count[] = new int [R + 1 ]; // 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 Code public static void main(String[] args) { int mat[][] = {{ 0 , 1 , 0 , 1 , 0 }, { 0 , 1 , 0 , 1 , 1 }, { 1 , 1 , 0 , 1 , 0 }}; System.out.println( "Area of the largest rectangle is " + maxArea(mat)); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python 3 program to find the largest # rectangle of 1's with swapping # of columns allowed. R = 3 C = 5 # Returns area of the largest # rectangle of 1's def maxArea(mat): # An auxiliary array to store count # of consecutive 1's in every column. hist = [[ 0 for i in range (C + 1 )] for i in range (R + 1 )] # Step 1: Fill the auxiliary array hist[][] for i in range ( 0 , C, 1 ): # First row in hist[][] is copy of # first row in mat[][] hist[ 0 ][i] = mat[ 0 ][i] # Fill remaining rows of hist[][] for j in range ( 1 , R, 1 ): if ((mat[j][i] = = 0 )): hist[j][i] = 0 else : hist[j][i] = hist[j - 1 ][i] + 1 # Step 2: Sort rows of hist[][] in # non-increasing order for i in range ( 0 , R, 1 ): count = [ 0 for i in range (R + 1 )] # counting occurrence for j in range ( 0 , C, 1 ): count[hist[i][j]] + = 1 # Traverse the count array from # right side col_no = 0 j = R while (j > = 0 ): if (count[j] > 0 ): for k in range ( 0 , count[j], 1 ): hist[i][col_no] = j col_no + = 1 j - = 1 # Step 3: Traverse the sorted hist[][] # to find maximum area max_area = 0 for i in range ( 0 , R, 1 ): for j in range ( 0 , C, 1 ): # 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 Code if __name__ = = '__main__' : mat = [[ 0 , 1 , 0 , 1 , 0 ], [ 0 , 1 , 0 , 1 , 1 ], [ 1 , 1 , 0 , 1 , 0 ]] print ( "Area of the largest rectangle is" , maxArea(mat)) # This code is contributed by # Shashank_Sharma |
C#
// C# program to find the largest rectangle of // 1's with swapping of columns allowed. using System; class GFG { static readonly int R = 3; static readonly int C = 5; // Returns area of the largest // rectangle of 1's static int maxArea( int [,]mat) { // An auxiliary array to store count // of consecutive 1's in every column. int [,]hist = new int [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 rows of hist[,] // in non-increasing order for ( int i = 0; i < R; i++) { int []count = new int [R + 1]; // 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 Code public static void Main() { int [,]mat = {{0, 1, 0, 1, 0}, {0, 1, 0, 1, 1}, {1, 1, 0, 1, 0}}; Console.WriteLine( "Area of the largest rectangle is " + maxArea(mat)); } } //This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to find the largest rectangle of // 1's with swapping of columns allowed. var R = 3; var C = 5; // Returns area of the largest // rectangle of 1's function maxArea(mat) { // An auxiliary array to store count // of consecutive 1's in every column. var hist = Array.from(Array(R+1), ()=>Array(C+1)); // Step 1: Fill the auxiliary array hist[,] for ( var 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 ( var j = 1; j < R; j++) { hist[j][i] = (mat[j][i] == 0) ? 0 : hist[j - 1][i] + 1; } } // Step 2: Sort rows of hist[,] // in non-increasing order for ( var i = 0; i < R; i++) { var count = Array(R+1).fill(0); // counting occurrence for ( var j = 0; j < C; j++) { count[hist[i][j]]++; } // Traverse the count array from right side var col_no = 0; for ( var j = R; j >= 0; j--) { if (count[j] > 0) { for ( var k = 0; k < count[j]; k++) { hist[i][col_no] = j; col_no++; } } } } // Step 3: Traverse the sorted hist[,] // to find maximum area var curr_area, max_area = 0; for ( var i = 0; i < R; i++) { for ( var 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 Code var mat = [[0, 1, 0, 1, 0], [0, 1, 0, 1, 1], [1, 1, 0, 1, 0]]; document.write( "Area of the largest rectangle is " + maxArea(mat)); </script> |
输出：
Area of the largest rectangle is 6
时间复杂性 上面的解是O（R*（R+C）），其中R是输入矩阵中的行数，C是列数。 额外空间 ：O（R*C） 本文由 希夫普拉萨德·乔杜里 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
