Dada una array con 0 y 1, encuentre el rectángulo más grande de todos los 1 en la array. El rectángulo se puede formar intercambiando cualquier par de columnas de la array dada.
Ejemplo:
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
La idea es usar una array auxiliar para almacenar el conteo de 1 consecutivos en cada columna. Una vez que tenemos estos conteos, clasificamos todas las filas de la array auxiliar en orden de conteo no creciente. Finalmente, recorra las filas ordenadas para encontrar el área máxima.
Nota: Después de formar la array auxiliar, cada fila se vuelve independiente, por lo tanto, podemos intercambiar u ordenar cada fila de forma independiente. Esto se debe a que solo podemos intercambiar columnas, por lo que hemos hecho que cada fila sea independiente y encontramos el área máxima de rectángulo posible con fila y columna. .
A continuación se detallan los pasos para el primer ejemplo mencionado anteriormente.
Paso 1: En primer lugar, calcule no. de 1 consecutivos en cada columna. Se utiliza una array auxiliar hist[][] para almacenar los recuentos de 1 consecutivos. Entonces, para el primer ejemplo anterior, el contenido de hist[R][C] sería
0 1 0 1 0
0 2 0 2 1
1 3 0 3 0
La complejidad temporal de este paso es O(R*C)
Paso 2: ordenar las filas de forma no creciente. Después de ordenar el paso, la array hist[][] sería
1 1 0 0 0
2 2 1 0 0
3 3 1 0 0
Este paso se puede hacer en O(R * (R + C)). Como sabemos que los valores están en el rango de 0 a R, podemos usar la ordenación por conteo para cada fila.
La clasificación es en realidad el intercambio de columnas. Si observamos la 3.ª fila en el paso 2:
3 3 1 0 0
La fila ordenada corresponde a intercambiar las columnas de modo que la columna con el rectángulo más alto posible se coloque primero, después viene la columna que permite el segundo rectángulo más alto y así en. Entonces, en el ejemplo hay 2 columnas que pueden formar un rectángulo de altura 3. Eso hace un área de 3*2=6. Si tratamos de hacer que el rectángulo sea más ancho, la altura cae a 1, porque no quedan columnas que permitan un rectángulo más alto en la tercera fila.
Paso 3:Recorra cada fila de hist[][] y verifique el área máxima. Dado que cada fila se ordena por recuento de 1, el área actual se puede calcular multiplicando el número de columna con el valor en hist[i][j]. Este paso también requiere tiempo O(R * C).
A continuación se muestra la implementación basada en la idea anterior.
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>
Producción:
Area of the largest rectangle is 6
La complejidad temporal de la solución anterior es O(R * (R + C)) donde R es el número de filas y C es el número de columnas en la array de entrada. Espacio adicional : O(R * C)
Este artículo es una contribución de Shivprasad Choudhary . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA