Dada una array binaria, encuentre la subarray binaria de rectángulo de tamaño máximo con todos 1.
Ejemplo:
Input: 0 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 Output : 8 Explanation : The largest rectangle with only 1's is from (1, 0) to (2, 3) which is 1 1 1 1 1 1 1 1 Input: 0 1 1 1 1 1 0 1 1 Output: 6 Explanation : The largest rectangle with only 1's is from (0, 1) to (2, 2) which is 1 1 1 1 1 1
Ya hay un algoritmo discutido una solución basada en programación dinámica para encontrar el cuadrado más grande con 1s .
Acercarse:
En esta publicación, se analiza un método interesante que utiliza el rectángulo más grande debajo del histograma como subrutina.
Si se proporciona la altura de las barras del histograma, se puede encontrar el área más grande del histograma. De esta forma en cada fila se encuentra la mayor área de barras del histograma. Para obtener el rectángulo más grande lleno de 1, actualice la siguiente fila con la fila anterior y encuentre el área más grande debajo del histograma, es decir, considere cada 1 como cuadrados llenos y los 0 con un cuadrado vacío y considere cada fila como la base.
Ilustración:
Input : 0 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 Step 1: 0 1 1 0 maximum area = 2 Step 2: row 1 1 2 2 1 area = 4, maximum area becomes 4 row 2 2 3 3 2 area = 8, maximum area becomes 8 row 3 3 4 0 0 area = 6, maximum area remains 8
Algoritmo:
- Ejecute un bucle para atravesar las filas.
- Ahora, si la fila actual no es la primera fila, actualice la fila de la siguiente manera, si array[i][j] no es cero, entonces array[i][j] = array[i-1][j] + array[i ][j].
- Encuentre el área rectangular máxima debajo del histograma, considere la i-ésima fila como alturas de barras de un histograma. Esto se puede calcular como se indica en este artículo Área rectangular más grande en un histograma
- Realice los dos pasos anteriores para todas las filas e imprima el área máxima de todas las filas.
Nota: Se recomienda encarecidamente consultar primero esta publicación, ya que la mayor parte del código se extrae de allí.
Implementación
C++
// C++ program to find largest
// rectangle with all 1s
// in a binary matrix
#include <bits/stdc++.h>
using namespace std;
// Rows and columns in input matrix
#define R 4
#define C 4
// Finds the maximum area under
// the histogram represented
// by histogram. See below article for details.
int maxHist(int row[])
{
// Create an empty stack.
// The stack holds indexes of
// hist[] array/ The bars stored
// in stack are always
// in increasing order of their heights.
stack<int> result;
int top_val; // Top of stack
int max_area = 0; // Initialize max area in current
// row (or histogram)
int area = 0; // Initialize area with current top
// Run through all bars of given histogram (or row)
int i = 0;
while (i < C) {
// If this bar is higher than the bar on top stack,
// push it to stack
if (result.empty() || row[result.top()] <= row[i])
result.push(i++);
else {
// If this bar is lower than top of stack, then
// calculate area of rectangle with stack top as
// the smallest (or minimum height) bar. 'i' is
// 'right index' for the top and element before
// top in stack is 'left index'
top_val = row[result.top()];
result.pop();
area = top_val * i;
if (!result.empty())
area = top_val * (i - result.top() - 1);
max_area = max(area, max_area);
}
}
// Now pop the remaining bars from stack and calculate
// area with every popped bar as the smallest bar
while (!result.empty()) {
top_val = row[result.top()];
result.pop();
area = top_val * i;
if (!result.empty())
area = top_val * (i - result.top() - 1);
max_area = max(area, max_area);
}
return max_area;
}
// Returns area of the largest rectangle with all 1s in
// A[][]
int maxRectangle(int A[][C])
{
// Calculate area for first row and initialize it as
// result
int result = maxHist(A[0]);
// iterate over row to find maximum rectangular area
// considering each row as histogram
for (int i = 1; i < R; i++) {
for (int j = 0; j < C; j++)
// if A[i][j] is 1 then add A[i -1][j]
if (A[i][j])
A[i][j] += A[i - 1][j];
// Update result if area with current row (as last
// row) of rectangle) is more
result = max(result, maxHist(A[i]));
}
return result;
}
// Driver code
int main()
{
int A[][C] = {
{ 0, 1, 1, 0 },
{ 1, 1, 1, 1 },
{ 1, 1, 1, 1 },
{ 1, 1, 0, 0 },
};
cout << "Area of maximum rectangle is "
<< maxRectangle(A);
return 0;
}
Java
// Java program to find largest rectangle with all 1s
// in a binary matrix
import java.io.*;
import java.util.*;
class GFG {
// Finds the maximum area under the histogram
// represented by histogram. See below article for
static int maxHist(int R, int C, int row[])
{
// Create an empty stack. The stack holds indexes of
// hist[] array/ The bars stored in stack are always
// in increasing order of their heights.
Stack<Integer> result = new Stack<Integer>();
int top_val; // Top of stack
int max_area = 0; // Initialize max area in current
// row (or histogram)
int area = 0; // Initialize area with current top
// Run through all bars of given histogram (or row)
int i = 0;
while (i < C) {
// If this bar is higher than the bar on top
// stack, push it to stack
if (result.empty()
|| row[result.peek()] <= row[i])
result.push(i++);
else {
// If this bar is lower than top of stack,
// then calculate area of rectangle with
// stack top as the smallest (or minimum
// height) bar. 'i' is 'right index' for the
// top and element before top in stack is
// 'left index'
top_val = row[result.peek()];
result.pop();
area = top_val * i;
if (!result.empty())
area
= top_val * (i - result.peek() - 1);
max_area = Math.max(area, max_area);
}
}
// Now pop the remaining bars from stack and
// calculate area with every popped bar as the
// smallest bar
while (!result.empty()) {
top_val = row[result.peek()];
result.pop();
area = top_val * i;
if (!result.empty())
area = top_val * (i - result.peek() - 1);
max_area = Math.max(area, max_area);
}
return max_area;
}
// Returns area of the largest rectangle with all 1s in
// A[][]
static int maxRectangle(int R, int C, int A[][])
{
// Calculate area for first row and initialize it as
// result
int result = maxHist(R, C, A[0]);
// iterate over row to find maximum rectangular area
// considering each row as histogram
for (int i = 1; i < R; i++) {
for (int j = 0; j < C; j++)
// if A[i][j] is 1 then add A[i -1][j]
if (A[i][j] == 1)
A[i][j] += A[i - 1][j];
// Update result if area with current row (as
// last row of rectangle) is more
result = Math.max(result, maxHist(R, C, A[i]));
}
return result;
}
// Driver code
public static void main(String[] args)
{
int R = 4;
int C = 4;
int A[][] = {
{ 0, 1, 1, 0 },
{ 1, 1, 1, 1 },
{ 1, 1, 1, 1 },
{ 1, 1, 0, 0 },
};
System.out.print("Area of maximum rectangle is "
+ maxRectangle(R, C, A));
}
}
// Contributed by Prakriti Gupta
Python3
# Python3 program to find largest rectangle
# with all 1s in a binary matrix
# Finds the maximum area under the
# histogram represented
# by histogram. See below article for details.
class Solution():
def maxHist(self, row):
# Create an empty stack. The stack holds
# indexes of hist array / The bars stored
# in stack are always in increasing order
# of their heights.
result = []
# Top of stack
top_val = 0
# Initialize max area in current
max_area = 0
# row (or histogram)
area = 0 # Initialize area with current top
# Run through all bars of given
# histogram (or row)
i = 0
while (i < len(row)):
# If this bar is higher than the
# bar on top stack, push it to stack
if (len(result) == 0) or (row[result[-1]] <= row[i]):
result.append(i)
i += 1
else:
# If this bar is lower than top of stack,
# then calculate area of rectangle with
# stack top as the smallest (or minimum
# height) bar. 'i' is 'right index' for
# the top and element before top in stack
# is 'left index'
top_val = row[result.pop()]
area = top_val * i
if (len(result)):
area = top_val * (i - result[-1] - 1)
max_area = max(area, max_area)
# Now pop the remaining bars from stack
# and calculate area with every popped
# bar as the smallest bar
while (len(result)):
top_val = row[result.pop()]
area = top_val * i
if (len(result)):
area = top_val * (i - result[-1] - 1)
max_area = max(area, max_area)
return max_area
# Returns area of the largest rectangle
# with all 1s in A
def maxRectangle(self, A):
# Calculate area for first row and
# initialize it as result
result = self.maxHist(A[0])
# iterate over row to find maximum rectangular
# area considering each row as histogram
for i in range(1, len(A)):
for j in range(len(A[i])):
# if A[i][j] is 1 then add A[i -1][j]
if (A[i][j]):
A[i][j] += A[i - 1][j]
# Update result if area with current
# row (as last row) of rectangle) is more
result = max(result, self.maxHist(A[i]))
return result
# Driver Code
if __name__ == '__main__':
A = [[0, 1, 1, 0],
[1, 1, 1, 1],
[1, 1, 1, 1],
[1, 1, 0, 0]]
ans = Solution()
print("Area of maximum rectangle is",
ans.maxRectangle(A))
# This code is contributed
# by Aaryaman Sharma
C#
// C# program to find largest rectangle
// with all 1s in a binary matrix
using System;
using System.Collections.Generic;
class GFG {
// Finds the maximum area under the
// histogram represented by histogram.
// See below article for details.
// https://
// www.geeksforgeeks.org/largest-rectangle-under-histogram/
public static int maxHist(int R, int C, int[] row)
{
// Create an empty stack. The stack
// holds indexes of hist[] array.
// The bars stored in stack are always
// in increasing order of their heights.
Stack<int> result = new Stack<int>();
int top_val; // Top of stack
int max_area = 0; // Initialize max area in
// current row (or histogram)
int area = 0; // Initialize area with
// current top
// Run through all bars of
// given histogram (or row)
int i = 0;
while (i < C) {
// If this bar is higher than the
// bar on top stack, push it to stack
if (result.Count == 0
|| row[result.Peek()] <= row[i]) {
result.Push(i++);
}
else {
// If this bar is lower than top
// of stack, then calculate area of
// rectangle with stack top as
// the smallest (or minimum height)
// bar. 'i' is 'right index' for
// the top and element before
// top in stack is 'left index'
top_val = row[result.Peek()];
result.Pop();
area = top_val * i;
if (result.Count > 0) {
area
= top_val * (i - result.Peek() - 1);
}
max_area = Math.Max(area, max_area);
}
}
// Now pop the remaining bars from
// stack and calculate area with
// every popped bar as the smallest bar
while (result.Count > 0) {
top_val = row[result.Peek()];
result.Pop();
area = top_val * i;
if (result.Count > 0) {
area = top_val * (i - result.Peek() - 1);
}
max_area = Math.Max(area, max_area);
}
return max_area;
}
// Returns area of the largest
// rectangle with all 1s in A[][]
public static int maxRectangle(int R, int C, int[][] A)
{
// Calculate area for first row
// and initialize it as result
int result = maxHist(R, C, A[0]);
// iterate over row to find
// maximum rectangular area
// considering each row as histogram
for (int i = 1; i < R; i++) {
for (int j = 0; j < C; j++) {
// if A[i][j] is 1 then
// add A[i -1][j]
if (A[i][j] == 1) {
A[i][j] += A[i - 1][j];
}
}
// Update result if area with current
// row (as last row of rectangle) is more
result = Math.Max(result, maxHist(R, C, A[i]));
}
return result;
}
// Driver code
public static void Main(string[] args)
{
int R = 4;
int C = 4;
int[][] A
= new int[][] { new int[] { 0, 1, 1, 0 },
new int[] { 1, 1, 1, 1 },
new int[] { 1, 1, 1, 1 },
new int[] { 1, 1, 0, 0 } };
Console.Write("Area of maximum rectangle is "
+ maxRectangle(R, C, A));
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript program to find largest rectangle
// with all 1s in a binary matrix
// Finds the maximum area under the
// histogram represented by histogram.
// See below article for details.
// https://
// www.geeksforgeeks.org/largest-rectangle-under-histogram/
function maxHist(R, C, row)
{
// Create an empty stack. The stack
// holds indexes of hist[] array.
// The bars stored in stack are always
// in increasing order of their heights.
let result = [];
let top_val; // Top of stack
let max_area = 0; // Initialize max area in
// current row (or histogram)
let area = 0; // Initialize area with
// current top
// Run through all bars of
// given histogram (or row)
let i = 0;
while (i < C) {
// If this bar is higher than the
// bar on top stack, push it to stack
if (result.length == 0
|| row[result[result.length - 1]] <= row[i]) {
result.push(i++);
}
else {
// If this bar is lower than top
// of stack, then calculate area of
// rectangle with stack top as
// the smallest (or minimum height)
// bar. 'i' is 'right index' for
// the top and element before
// top in stack is 'left index'
top_val = row[result[result.length - 1]];
result.pop();
area = top_val * i;
if (result.length > 0) {
area = top_val * (i - result[result.length - 1] - 1);
}
max_area = Math.max(area, max_area);
}
}
// Now pop the remaining bars from
// stack and calculate area with
// every popped bar as the smallest bar
while (result.length > 0) {
top_val = row[result[result.length - 1]];
result.pop();
area = top_val * i;
if (result.length > 0) {
area = top_val * (i - result[result.length - 1] - 1);
}
max_area = Math.max(area, max_area);
}
return max_area;
}
// Returns area of the largest
// rectangle with all 1s in A[][]
function maxRectangle(R, C, A)
{
// Calculate area for first row
// and initialize it as result
let result = maxHist(R, C, A[0]);
// iterate over row to find
// maximum rectangular area
// considering each row as histogram
for (let i = 1; i < R; i++) {
for (let j = 0; j < C; j++) {
// if A[i][j] is 1 then
// add A[i -1][j]
if (A[i][j] == 1) {
A[i][j] += A[i - 1][j];
}
}
// Update result if area with current
// row (as last row of rectangle) is more
result = Math.max(result, maxHist(R, C, A[i]));
}
return result;
}
let R = 4;
let C = 4;
let A = [ [ 0, 1, 1, 0 ],
[ 1, 1, 1, 1 ],
[ 1, 1, 1, 1 ],
[ 1, 1, 0, 0 ] ];
document.write("Area of maximum rectangle is "
+ maxRectangle(R, C, A));
// This code is contributed by decode2207.
</script>
Producción
Area of maximum rectangle is 8
Análisis de Complejidad:
- Complejidad Temporal: O(R x C).
Solo se requiere un recorrido de la array, por lo que la complejidad del tiempo es O (RXC) - Complejidad espacial: O(C).
Se requiere pila para almacenar las columnas, por lo que la complejidad del espacio es O (C)
Este artículo es una contribución de Sanjiv Kumar. Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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