área rectangular más grande en un histograma | conjunto 2

 

Encuentre el área rectangular más grande posible en un histograma dado donde el rectángulo más grande puede estar formado por varias barras contiguas. Para simplificar, suponga que todas las barras tienen el mismo ancho y el ancho es 1 unidad. 
Por ejemplo, considere el siguiente histograma con 7 barras de alturas {6, 2, 5, 4, 5, 1, 6}. El rectángulo más grande posible es 12 (vea la figura a continuación, el rectángulo de área máxima está resaltado en rojo)
 

histogram

 

Hemos discutido una solución O(nLogn) basada en Divide and Conquer para este problema. En esta publicación, se discute la solución de tiempo O(n). Al igual que en la publicación anterior , se supone que el ancho de todas las barras es 1 por simplicidad. Para cada barra ‘x’, calculamos el área con ‘x’ como la barra más pequeña del rectángulo. Si calculamos dicha área para cada barra ‘x’ y encontramos el máximo de todas las áreas, nuestra tarea está hecha. ¿Cómo calcular el área con ‘x’ como barra más pequeña? Necesitamos saber el índice de la primera barra más pequeña (menor que ‘x’) a la izquierda de ‘x’ y el índice de la primera barra más pequeña a la derecha de ‘x’. Llamemos a estos índices como ‘índice izquierdo’ e ‘índice derecho’ respectivamente. 
Atravesamos todas las barras de izquierda a derecha, mantenemos una pila de barras. Cada barra se empuja para apilar una vez. Una barra sale de la pila cuando se ve una barra de menor altura. Cuando se abre una barra, calculamos el área con la barra emergente como la barra más pequeña. ¿Cómo obtenemos los índices izquierdo y derecho de la barra emergente? El índice actual nos dice el ‘índice derecho’ y el índice del elemento anterior en la pila es el ‘índice izquierdo’. A continuación se muestra el algoritmo completo.
1) Crea una pila vacía.
2) Comience desde la primera barra y siga para cada barra ‘hist[i]’ donde ‘i’ varía de 0 a n-1. 
…… a) Si la pila está vacía o hist[i] es más alto que la barra en la parte superior de la pila, presione ‘i’ para apilar. 
…… b)Si esta barra es más pequeña que la parte superior de la pila, siga quitando la parte superior de la pila mientras la parte superior de la pila sea mayor. Deje que la barra eliminada sea hist[tp]. Calcula el área del rectángulo con hist[tp] como la barra más pequeña. Para hist[tp], el ‘índice izquierdo’ es el elemento anterior (anterior a tp) en la pila y el ‘índice derecho’ es ‘i’ (índice actual).
3) Si la pila no está vacía, retire todas las barras de la pila una por una y realice el paso 2.b para cada barra eliminada.

A continuación se muestra la implementación del algoritmo anterior. 

C++

// C++ program to find maximum rectangular area in
// linear time
#include<bits/stdc++.h>
using namespace std;
 
// The main function to find the maximum rectangular
// area under given histogram with n bars
int getMaxArea(int hist[], int n)
{
    // 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> s;
 
    int max_area = 0; // Initialize max area
    int tp;  // To store top of stack
    int area_with_top; // To store area with top bar
                       // as the smallest bar
 
    // Run through all bars of given histogram
    int i = 0;
    while (i < n)
    {
        // If this bar is higher than the bar on top
        // stack, push it to stack
        if (s.empty() || hist[s.top()] <= hist[i])
            s.push(i++);
 
        // 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'
        else
        {
            tp = s.top();  // store the top index
            s.pop();  // pop the top
 
            // Calculate the area with hist[tp] stack
            // as smallest bar
            area_with_top = hist[tp] * (s.empty() ? i :
                                   i - s.top() - 1);
 
            // update max area, if needed
            if (max_area < area_with_top)
                max_area = area_with_top;
        }
    }
 
    // Now pop the remaining bars from stack and calculate
    // area with every popped bar as the smallest bar
    while (s.empty() == false)
    {
        tp = s.top();
        s.pop();
        area_with_top = hist[tp] * (s.empty() ? i :
                                i - s.top() - 1);
 
        if (max_area < area_with_top)
            max_area = area_with_top;
    }
 
    return max_area;
}
 
// Driver program to test above function
int main()
{
    int hist[] = {6, 2, 5, 4, 5, 1, 6};
    int n = sizeof(hist)/sizeof(hist[0]);
    cout << "Maximum area is " << getMaxArea(hist, n);
    return 0;
}

Java

//Java program to find maximum rectangular area in linear time
 
import java.util.Stack;
 
public class RectArea
{
    // The main function to find the maximum rectangular area under given
    // histogram with n bars
    static int getMaxArea(int hist[], int n)
    {
        // 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> s = new Stack<>();
         
        int max_area = 0; // Initialize max area
        int tp;  // To store top of stack
        int area_with_top; // To store area with top bar as the smallest bar
      
        // Run through all bars of given histogram
        int i = 0;
        while (i < n)
        {
            // If this bar is higher than the bar on top stack, push it to stack
            if (s.empty() || hist[s.peek()] <= hist[i])
                s.push(i++);
      
            // 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'
            else
            {
                tp = s.peek();  // store the top index
                s.pop();  // pop the top
      
                // Calculate the area with hist[tp] stack as smallest bar
                area_with_top = hist[tp] * (s.empty() ? i : i - s.peek() - 1);
      
                // update max area, if needed
                if (max_area < area_with_top)
                    max_area = area_with_top;
            }
        }
      
        // Now pop the remaining bars from stack and calculate area with every
        // popped bar as the smallest bar
        while (s.empty() == false)
        {
            tp = s.peek();
            s.pop();
            area_with_top = hist[tp] * (s.empty() ? i : i - s.peek() - 1);
      
            if (max_area < area_with_top)
                max_area = area_with_top;
        }
      
        return max_area;
 
    }
     
    // Driver program to test above function
    public static void main(String[] args)
    {
        int hist[] = { 6, 2, 5, 4, 5, 1, 6 };
        System.out.println("Maximum area is " + getMaxArea(hist, hist.length));
    }
}
//This code is Contributed by Sumit Ghosh

Python3

# Python3 program to find maximum
# rectangular area in linear time
 
def max_area_histogram(histogram):
     
    # This function calculates maximum
    # rectangular area under given
    # histogram with n bars
 
    # Create an empty stack. The stack
    # holds indexes of histogram[] list.
    # The bars stored in the stack are
    # always in increasing order of
    # their heights.
    stack = list()
 
    max_area = 0 # Initialize max area
 
    # Run through all bars of
    # given histogram
    index = 0
    while index < len(histogram):
         
        # If this bar is higher
        # than the bar on top
        # stack, push it to stack
 
        if (not stack) or (histogram[stack[-1]] <= histogram[index]):
            stack.append(index)
            index += 1
 
        # 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'
        else:
            # pop the top
            top_of_stack = stack.pop()
 
            # Calculate the area with
            # histogram[top_of_stack] stack
            # as smallest bar
            area = (histogram[top_of_stack] *
                   ((index - stack[-1] - 1)
                   if stack else index))
 
            # update max area, if needed
            max_area = max(max_area, area)
 
    # Now pop the remaining bars from
    # stack and calculate area with
    # every popped bar as the smallest bar
    while stack:
         
        # pop the top
        top_of_stack = stack.pop()
 
        # Calculate the area with
        # histogram[top_of_stack]
        # stack as smallest bar
        area = (histogram[top_of_stack] *
              ((index - stack[-1] - 1)
                if stack else index))
 
        # update max area, if needed
        max_area = max(max_area, area)
 
    # Return maximum area under
    # the given histogram
    return max_area
 
# Driver Code
hist = [6, 2, 5, 4, 5, 1, 6]
print("Maximum area is",
       max_area_histogram(hist))
 
# This code is contributed
# by Jinay Shah

C#

// C# program to find maximum
// rectangular area in linear time
using System;
using System.Collections.Generic;
 
class GFG
{
// The main function to find the
// maximum rectangular area under
// given histogram with n bars
public static int getMaxArea(int[] hist,
                             int n)
{
    // 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> s = new Stack<int>();
 
    int max_area = 0; // Initialize max area
    int tp; // To store top of stack
    int area_with_top; // To store area with top
                       // bar as the smallest bar
 
    // Run through all bars of
    // given histogram
    int i = 0;
    while (i < n)
    {
        // If this bar is higher than the
        // bar on top stack, push it to stack
        if (s.Count == 0 || hist[s.Peek()] <= hist[i])
        {
            s.Push(i++);
        }
 
        // 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'
        else
        {
            tp = s.Peek(); // store the top index
            s.Pop(); // pop the top
 
            // Calculate the area with hist[tp]
            // stack as smallest bar
            area_with_top = hist[tp] *
                           (s.Count == 0 ? i : i - s.Peek() - 1);
 
            // update max area, if needed
            if (max_area < area_with_top)
            {
                max_area = area_with_top;
            }
        }
    }
 
    // Now pop the remaining bars from
    // stack and calculate area with every
    // popped bar as the smallest bar
    while (s.Count > 0)
    {
        tp = s.Peek();
        s.Pop();
        area_with_top = hist[tp] *
                       (s.Count == 0 ? i : i - s.Peek() - 1);
 
        if (max_area < area_with_top)
        {
            max_area = area_with_top;
        }
    }
 
    return max_area;
 
}
 
// Driver Code
public static void Main(string[] args)
{
    int[] hist = new int[] {6, 2, 5, 4, 5, 1, 6};
    Console.WriteLine("Maximum area is " +
                       getMaxArea(hist, hist.Length));
}
}
 
// This code is contributed by Shrikant13

Javascript

<script>
 
// JavaScript program to find maximum
// rectangular area in linear time
 
function max_area_histogram(histogram){
     
    // This function calculates maximum
    // rectangular area under given
    // histogram with n bars
 
    // Create an empty stack. The stack
    // holds indexes of histogram[] list.
    // The bars stored in the stack are
    // always in increasing order of
    // their heights.
    let stack = []
 
    let max_area = 0 // Initialize max area
 
    // Run through all bars of
    // given histogram
    let index = 0
    while(index < histogram.length){
         
        // If this bar is higher
        // than the bar on top
        // stack, push it to stack
 
        if(stack.length == 0 || histogram[stack[stack.length-1]] <= histogram[index]){
            stack.push(index)
            index += 1
        }
 
        // 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'
        else{
            // pop the top
            let top_of_stack = stack.pop()
 
            // Calculate the area with
            // histogram[top_of_stack] stack
            // as smallest bar
            let area = (histogram[top_of_stack] *
                (stack.length > 0 ? (index - stack[stack.length-1] - 1) : index))
 
            // update max area, if needed
            max_area = Math.max(max_area, area)
        }
    }
    // Now pop the remaining bars from
    // stack and calculate area with
    // every popped bar as the smallest bar
    while(stack.length > 0){
         
        // pop the top
        let top_of_stack = stack.pop()
 
        // Calculate the area with
        // histogram[top_of_stack]
        // stack as smallest bar
        let area = (histogram[top_of_stack] *
            (stack.length > 0 ? (index - stack[stack.length-1] - 1) : index))
 
        // update max area, if needed
        max_area = Math.max(max_area, area)
    }
 
    // Return maximum area under
    // the given histogram
    return max_area
}
 
// Driver Code
let hist = [6, 2, 5, 4, 5, 1, 6]
document.write("Maximum area is", max_area_histogram(hist))
 
// This code is contributed
// by shinjanpatra
 
</script>
Producción

Maximum area is 12

Complejidad de tiempo: dado que cada barra se presiona y se abre solo una vez, la complejidad de tiempo de este método es O (n).

Otro enfoque eficiente:   al encontrar el siguiente elemento más pequeño y el elemento más pequeño anterior para cada elemento en O (n) complejidad de tiempo y O (n) espacio auxiliar .

Paso 1: Primero tomaremos dos arrays left_smaller[] y right_smaller[] e inicializaremos con -1 y n respectivamente.

Paso 2: para cada elemento, almacenaremos el índice del elemento anterior más pequeño y el siguiente más pequeño en las arrays left_smaller[] y right_smaller[] respectivamente.

                (Tomará O(n) tiempo).

Paso 3: Ahora, para cada elemento, calcularemos el área tomando este i-ésimo elemento como el más pequeño en el rango, más pequeño_izquierdo[i] y más pequeño_derecho[i] y multiplicándolo por la diferencia de más pequeño_izquierdo[i] y más pequeño_derecho[i].

Paso 4: podemos encontrar el máximo de toda el área calculada en el paso 3 para obtener el área máxima deseada.

C++

#include <bits/stdc++.h>
using namespace std;
 
 
//Function to find largest rectangular area possible in a given histogram.
int getMaxArea(int arr[], int n)
{
    // Your code here
    //we create an empty stack here.
    stack<int> s;
    //we push -1 to the stack because for some elements there will be no previous
    //smaller element in the array and we can store -1 as the index for previous smaller.
    s.push(-1);
    int area = arr[0];
    int i = 0;
    //We declare left_smaller and right_smaller array of size n and initialize them with -1 and n as their default value.
    //left_smaller[i] will store the index of previous smaller element for ith element of the array.
    //right_smaller[i] will store the index of next smaller element for ith element of the array.
    vector<int> left_smaller(n, -1), right_smaller(n, n);
    while(i<n){
        while(!s.empty()&&s.top()!=-1&&arr[s.top()]>arr[i]){
            //if the current element is smaller than element with index stored on the
            //top of stack then, we pop the top element and store the current element index
            //as the right_smaller for the popped element.
            right_smaller[s.top()] = i;
            s.pop();
        }
        if(i>0&&arr[i]==arr[i-1]){
            //we use this condition to avoid the unnecessary loop to find the left_smaller.
            //since the previous element is same as current element, the left_smaller will always be the same for both.
            left_smaller[i] = left_smaller[i-1];
        }else{
            //Element with the index stored on the top of the stack is always smaller than the current element.
            //Therefore the left_smaller[i] will always be s.top().
            left_smaller[i] = s.top();
        } 
        s.push(i);
        i++;
    }
    for(int j = 0; j<n; j++){
        //here we find area with every element as the smallest element in their range and compare it with the previous area.
        // in this way we get our max Area form this.
        area = max(area, arr[j]*(right_smaller[j]-left_smaller[j]-1));
    }
    return area;
}
 
int main()
 {
    int hist[] = {6, 2, 5, 4, 5, 1, 6};
    int n = sizeof(hist)/sizeof(hist[0]);
      cout << "maxArea = " << getMaxArea(hist, n) << endl;
    return 0;
}
 
//This code is Contributed by Arunit Kumar.

Java

import java.util.*;
import java.lang.*;
import java.io.*;
 
public class RectArea
{
     
    //Function to find largest rectangular area possible in a given histogram.
    public static int getMaxArea(int arr[], int n)
    {
        // your code here
        //we create an empty stack here.
        Stack<Integer> s = new Stack<>();
        //we push -1 to the stack because for some elements there will be no previous
        //smaller element in the array and we can store -1 as the index for previous smaller.
        s.push(-1);
        int max_area = arr[0];
        //We declare left_smaller and right_smaller array of size n and initialize them with -1 and n as their default value.
        //left_smaller[i] will store the index of previous smaller element for ith element of the array.
        //right_smaller[i] will store the index of next smaller element for ith element of the array.
        int left_smaller[] = new int[n];
        int right_smaller[] = new int[n];
        for (int i = 0; i < n; i++){
            left_smaller[i] = -1;
            right_smaller[i] = n;
        }
 
        int i = 0;
        while (i < n)
        {
            while(!s.empty()&&s.peek()!=-1&&arr[i]<arr[s.peek()]){
                //if the current element is smaller than element with index stored on the
                //top of stack then, we pop the top element and store the current element index
                //as the right_smaller for the popped element.
                right_smaller[s.peek()] = (int)i;
                s.pop();
            }
            if(i>0&&arr[i]==arr[(i-1)]){
                //we use this condition to avoid the unnecessary loop to find the left_smaller.
                //since the previous element is same as current element, the left_smaller will always be the same for both.
                left_smaller[i] = left_smaller[(int)(i-1)];
            }else{
                //Element with the index stored on the top of the stack is always smaller than the current element.
                //Therefore the left_smaller[i] will always be s.top().
                left_smaller[i] = s.peek();
            }
            s.push(i);
            i++;
        }
 
 
        for(i = 0; i<n; i++){
            //here we find area with every element as the smallest element in their range and compare it with the previous area.
            // in this way we get our max Area form this.
            max_area = Math.max(max_area, arr[i]*(right_smaller[i] - left_smaller[i] - 1));
        }
 
        return max_area;
    }
     
    public static void main(String[] args)
    {
        int hist[] = { 6, 2, 5, 4, 5, 1, 6 };
        System.out.println("Maximum area is " + getMaxArea(hist, hist.length));
    }
}
//This code is Contributed by Arunit Kumar.

Python3

#this is single line comment
"""
this
is
multiline
comment
"""
def getMaxArea(arr):
  s = [-1]
  n = len(arr)
  area = 0
  i = 0
  left_smaller = [-1]*n
  right_smaller = [n]*n
  while i < n:
      while s and (s[-1] != -1) and (arr[s[-1]] > arr[i]):
          right_smaller[s[-1]] = i
          s.pop()
      if((i > 0) and (arr[i] == arr[i-1])):
          left_smaller[i] = left_smaller[i-1]
      else:
          left_smaller[i] = s[-1]
      s.append(i)
      i += 1
  for j in range(0, n):
      area = max(area, arr[j]*(right_smaller[j]-left_smaller[j]-1))
  return area
 
hist = [6, 2, 5, 4, 5, 1, 6]
print("maxArea = ", getMaxArea(hist))
 
#This code is contributed by Arunit Kumar

C#

using System;
using System.Collections.Generic;
public class RectArea
{
 
  // Function to find largest rectangular area possible in a given histogram.
  public static int getMaxArea(int []arr, int n)
  {
 
    // your code here
    // we create an empty stack here.
    Stack<int> s = new Stack<int>();
 
    // we push -1 to the stack because for some elements there will be no previous
    // smaller element in the array and we can store -1 as the index for previous
    // smaller.
    s.Push(-1);
    int max_area = arr[0];
 
    // We declare left_smaller and right_smaller array of size n and initialize them
    // with -1 and n as their default value.
    // left_smaller[i] will store the index of previous smaller element for ith
    // element of the array.
    // right_smaller[i] will store the index of next smaller element for ith element
    // of the array.
    int []left_smaller = new int[n];
    int []right_smaller = new int[n];
    for (int j = 0; j < n; j++) {
      left_smaller[j] = -1;
      right_smaller[j] = n;
    }
 
    int i = 0;
    while (i < n) {
      while (s.Count !=0 && s.Peek() != -1 && arr[i] < arr[s.Peek()])
      {
 
        // if the current element is smaller than element with index stored on the
        // top of stack then, we pop the top element and store the current element index
        // as the right_smaller for the popped element.
        right_smaller[s.Peek()] = (int) i;
        s.Pop();
      }
      if (i > 0 && arr[i] == arr[(i - 1)])
      {
 
        // we use this condition to avoid the unnecessary loop to find the left_smaller.
        // since the previous element is same as current element, the left_smaller will
        // always be the same for both.
        left_smaller[i] = left_smaller[(int) (i - 1)];
      }
      else
      {
 
        // Element with the index stored on the top of the stack is always smaller than
        // the current element.
        // Therefore the left_smaller[i] will always be s.top().
        left_smaller[i] = s.Peek();
      }
      s.Push(i);
      i++;
    }
 
    for (i = 0; i < n; i++)
    {
 
      // here we find area with every element as the smallest element in their range
      // and compare it with the previous area.
      // in this way we get our max Area form this.
      max_area = Math.Max(max_area, arr[i] * (right_smaller[i] - left_smaller[i] - 1));
    }
 
    return max_area;
  }
 
  public static void Main(String[] args) {
    int []hist = { 6, 2, 5, 4, 5, 1, 6 };
    Console.WriteLine("Maximum area is " + getMaxArea(hist, hist.Length));
  }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
 
//Function to find largest rectangular area possible in a given histogram.
function getMaxArea(arr, n)
{
    // Your code here
    //we create an empty stack here.
    let s = [];
    //we push -1 to the stack because for some elements there will be no previous
    //smaller element in the array and we can store -1 as the index for previous smaller.
    s.push(-1);
    let area = arr[0];
    let i = 0;
    //We declare left_smaller and right_smaller array of size n and initialize them with -1 and n as their default value.
    //left_smaller[i] will store the index of previous smaller element for ith element of the array.
    //right_smaller[i] will store the index of next smaller element for ith element of the array.
    let left_smaller = new Array(n).fill(-1), right_smaller = new Array(n).fill(n);
    while(i<n){
        while(s.length > 0 &&s[s.length-1]!=-1&&arr[s[s.length-1]]>arr[i]){
            //if the current element is smaller than element with index stored on the
            //top of stack then, we pop the top element and store the current element index
            //as the right_smaller for the popped element.
            right_smaller[s[s.length-1]] = i;
            s.pop();
        }
        if(i>0&&arr[i]==arr[i-1]){
            //we use this condition to avoid the unnecessary loop to find the left_smaller.
            //since the previous element is same as current element, the left_smaller will always be the same for both.
            left_smaller[i] = left_smaller[i-1];
        }else{
            //Element with the index stored on the top of the stack is always smaller than the current element.
            //Therefore the left_smaller[i] will always be s[s.length-1].
            left_smaller[i] = s[s.length-1];
        } 
        s.push(i);
        i++;
    }
    for(let j = 0; j<n; j++){
        //here we find area with every element as the smallest element in their range and compare it with the previous area.
        // in this way we get our max Area form this.
        area = Math.max(area, arr[j]*(right_smaller[j]-left_smaller[j]-1));
    }
    return area;
}
 
// driver code
 
let hist = [6, 2, 5, 4, 5, 1, 6];
let n = hist.length;
document.write("maxArea = " + getMaxArea(hist, n));
 
// This code is contributed by shinjanpatra
 
</script>
Producción

maxArea = 12

Complejidad de tiempo :   O(n)

Complejidad espacial :   O(n)

Referencias  
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/histogram.html  
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge. html
Gracias a Ashish Anand por sugerir la solución inicial. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *