¿Cuál es el enfoque algorítmico para encontrar el área rectangular máxima en un histograma?

Aquí está la lógica a continuación, pero antes de eso se supone que el ancho de cada rectángulo de histograma es único.

Estructura de datos utilizaremos las alturas de los rectángulos de histograma y la pila de estructura de datos auxiliar para almacenar el índice de la matriz de altura procesada hasta el momento, que puede contribuir al cálculo del área rectangular (pero al explicar el proceso de despeje estaré almacenando la altura)

Como atravesaremos todo el conjunto de alturas de izquierda a derecha, inicialmente empujaremos la primera altura a la pila (que se utiliza para almacenar todo el grupo de alturas que puede conducir al área máxima del rectángulo).

1. A medida que recorremos el conjunto de alturas, compararemos la altura vista hasta ahora

(almacenado en la parte superior de la pila, correspondiente al índice de la matriz de entrada de altura) si su valor es menor con el elemento actual en la matriz de alturas, empujaremos el índice de la matriz de altura, porque en este último punto del tiempo puede conducir al área máxima debido al aumento de altura.

por ejemplo, si la matriz de altura es: {2,3,3,5,2} la pila actual contiene solo [{2}] aquí el área que será máxima se debe a 3 * 1 = 3. (3 = altura del histograma y el ancho es 1).
Después de que esta pila contenga será [{2,3}]

2. De lo contrario, verificaremos si es igual al elemento superior actual en la pila, si es así, continuaremos con la siguiente altura en la matriz, es porque esto se considerará más adelante para el cálculo del área, y además no habíamos atravesado el toda la matriz, por lo que no podemos asumir nada ahora.

por ejemplo, si la matriz de altura es: {2,3,3,5,2} la pila actual contiene solo [{2,3}] aquí el área que será máxima se debe a 3 * 2 = 6, si consideramos 3 como el siguiente elemento, pero es posible que también se puedan ver 3 en el futuro, por lo que simplemente lo ignoraremos, ya que ya está en la pila, se considerará para el cálculo del área si encontramos algo en el futuro que será más pequeño que esta altura {3}, ya que romperá la propiedad del rectángulo a esa altura futura. Después de esta pila contendrá [{2,3}]

entonces iremos al paso 1, ya que 5 es el siguiente elemento, por lo que es mayor en valor que la parte superior de la pila, por lo que lo empujaremos [{2,3,5}] – el contenido de la pila después de que se procese 5.

3. Sin embargo, si la altura en la matriz es menor que en la parte superior de la pila, debemos mostrar todos los elementos hasta que la altura en la parte superior de la pila sea menor que la altura actual o la pila se vacíe, ya que esta altura en la matriz Rompa la propiedad del rectángulo que mantenía la parte superior del elemento de pila.

por ejemplo, cuando procesaremos el último elemento en la pila que es 2, 5 debería aparecer, ya que la altura 2 no podrá completar la altura rectangular de 5. y continuaremos este proceso hasta que encontremos el elemento en la parte superior de la pila que es igual o menor en valor, que la altura actual.

Mediante el proceso anterior, también destacaremos el elemento elemento 3 y contribuirá con un área de 3 * 3 (ancho) = 9. Después de este contenido de pila será [{2}].

4. Si no hay más alturas para procesar, procesaremos el elemento restante en la pila.
con eso obtendremos el área máxima como 2 * 5 (ancho) = 10. Para aclaraciones, siga el código a continuación.

class MaxRectangularHistogram{ int calculateRectArea(int[] heights){ int size=heights.length; Stack st=new Stack(); int maxArea=0; for(int i=0;iheights[i]){ int data=st.pop(); lastIndex=data; if(heights[data]*(i-data)>maxArea) maxArea=heights[data]*(i-data); }else{ if(heights[st.top()]<=heights[i]) break; } } if(heights[st.top()]maxArea) maxArea=area[data]*(size-data); } return maxArea; } } 

Todas las respuestas basadas en la pila son absolutamente precisas, * pero * siempre encuentro que las respuestas basadas en la pila no son fáciles de mantener en mi cabeza (lo mismo con el algoritmo de Kadane), por lo que voy a proponer un programa más difícil, pero más fácil de manejar. Entender (dividir y conquistar) la solución.

1. Intuitivamente, el máximo. área rectangular es un área de altura en algún lugar entre el mínimo. y max. altura de una sola barra.
2. Comenzamos con la barra más pequeña y asumimos que la altura es su altura y el ancho es el ancho de todo el histograma.
3. Luego nos fijamos en las 2 sub-matrices que el min. se extiende por el rectángulo de altura y resuelve recursivamente esas 2 mitades.
4. Obtendremos O (n) soluciones (áreas), y el máximo de estas es la respuesta.

Ahora, podemos resolver el problema de encontrar la barra de valor mínimo en un rango resolviendo el problema RMQ (consulta de rango mínimo), que puede resolverse utilizando el procesamiento previo O (n) y el tiempo de consulta O (1).

¡¡Hemos terminado!!

Quora User lo logró, pero solo quería señalar que esta es una manifestación particular del problema de los valores más pequeños más cercanos (ANSV). Para cada barra en el histograma, queremos encontrar la barra más cercana a la izquierda, que es más corta, y la barra más cercana a la derecha, que es más corta, porque determinan qué tan a la izquierda y qué tan a la derecha podemos extender un rectángulo con la corriente altura total de la barra. Utilice el algoritmo basado en pila O (n) para ANSV, y el problema se vuelve trivial.

Primero, la solución que voy a proponer es exactamente similar a las que se analizan a continuación. Sin embargo, voy a explicar por qué funciona la mejor solución y cómo llegaron las personas a esa solución. Mi solución es esencialmente un trampolín entre la mejor solución y la solución forzada bruta.

No logré el rectángulo máximo usando solo 1 pila. Necesitaba 2 pilas y 2 matrices. Te mostraré por qué en un momento.

Deje que la matriz dada sea (Usando la misma matriz utilizada por Sumit a continuación):

A = {2, 3, 3, 5, 2}

Comencemos primero con la solución de fuerza bruta:

1. Para cada elemento de la matriz, exploramos a la izquierda y a la derecha la cantidad de elementos continuos que son mayores o iguales que el elemento actual y los almacenamos en 2 matrices. Llámalos a izquierda y derecha. (Esto explica por qué 2 matrices).
2. Nuestras matrices izquierda y derecha se verán así: left = {0,0,1,0,4}, right = {4,2,1,0,0}
3. Ahora agregue los valores en los mismos índices en ambas matrices. Luego agregue 1 a la suma resultante (izquierda [i] + derecha [i] + 1). Estamos agregando 1 para incluir el elemento actual. Esto nos da el ancho del rectángulo con altura A [i];
4. Por ejemplo, el Rectángulo que comienza en el índice 0 de A tendrá un área de (0 + 4 +1) * 2 = 5 * 2 = 10 unidades cuadradas.
5. Mantenga un registro del área máxima mientras realiza los pasos 3 y 4.

La complejidad de tiempo para esta solución será O (n ^ 2).

Como puede observar, el problema se vuelve trivial después de haber poblado nuestras matrices izquierda y derecha.

Centrémonos en minimizar la cantidad de trabajo realizado en rellenar matrices izquierda y derecha:

Comencemos por completar la matriz izquierda. Una vez que comprenda eso, la matriz correcta se puede completar en líneas similares.

La idea es la misma que el método de fuerza bruta. Sin embargo, no necesitamos mirar cada elemento para encontrar el número de elementos continuos mayor o igual que el elemento actual.

Por lo tanto, usamos 2 pilas. Vamos a llamarlos como height_stack y count_stack.

Una pila almacenará la altura del rectángulo (o los valores de la matriz) y la otra pila almacenará el recuento de elementos continuos en el lado izquierdo del elemento actual.

1. Coloque el primer elemento en height_stack y 0 en count_stack (ya que no hay elementos a la izquierda del primer elemento). Además, establecemos left [0] = 0. En nuestro caso, height_stack tendrá 2 y el count_stack 0. height_stack = {2} count_stack = {0} y left = {0}.
2. Comience a iterar desde el segundo elemento. Tenemos 2 opciones:
3. El elemento actual es menor o igual que la parte superior de height_stack o el elemento actual es mayor que la parte superior de height_stack.
4. Si el elemento actual es mayor que height_stack, simplemente empujamos el elemento actual en height_stack y 0 en count_stack. También actualizamos left [elemento actual] = 0. Para A [1], height_stack = {3,2} y count_stack = {0,0} y left [1] = 0.
5. Si el elemento actual es menor o igual que la parte superior de height_stack, sacamos los elementos de height_stack y count_stack. Seguimos apareciendo hasta que height_stack esté vacío o el elemento actual sea mayor que la parte superior de height_stack. Para A [2], height_stack = {3,2}, count_stack = {1,0}, izquierda [2] = 1.
6. Mientras estamos haciendo estallar elementos, seguimos agregando los elementos revelados de count_stack.
7. Una vez que alcanzamos cualquiera de las 2 condiciones del paso 5, empujamos la suma que obtuvimos en el paso 6 y el elemento actual en count_stack y height_stack, respectivamente. También actualizamos la matriz izquierda a izquierda [elemento actual] = suma del paso 6.

Continúe con los pasos 4,5,6 y 7 hasta llegar al último elemento de A. Como resultado, obtendremos un conteo en la matriz izquierda que tenga una altura mayor o igual que el elemento en el índice i.
Del mismo modo, podemos obtener la matriz correcta atravesando la matriz de entrada A de derecha a izquierda.
Una vez que obtenemos la matriz izquierda y derecha, solo tenemos que calcular el área como lo hicimos con la fuerza bruta.
En este enfoque, cada elemento se toca a lo sumo dos veces (uno al empujar y otro al estallar).

Por lo tanto, la complejidad del tiempo es O (n) y la complejidad del espacio también es O (n).

Amo esta solución en particular.

Aquí hay una publicación detallada que explica la solución en detalle (tal vez demasiado). Área más grande bajo un histograma (y conceptos / problemas relacionados).

Esencialmente, una vez que invierte el problema para encontrar los extremos para cada mínimo. Rápidamente se da cuenta de cómo modelar este problema en términos de qué memorizar en cada iteración, para expandir la solución actual. La memorización es una secuencia monotónicamente creciente, y la resolución de la pila es una forma realmente inteligente de mutar eso.

Los mejores recursos que pude encontrar que son relevantes para este problema son:

http://www.geeksforgeeks.org/lar …

http://www.geeksforgeeks.org/lar …

https://www.quora.com/What-is-th …

https://github.com/mission-peace …

Videos:

http://www.informatik.uni-ulm.de …

http://tech-queries.blogspot.in/ …

http://stackoverflow.com/questio …

Bueno, esto en un problema interesante se puede resolver de varias maneras.

El algoritmo más eficiente utiliza una estructura de datos de pila, en este

Enfoque descubrimos que es posible un rectángulo de área máxima debido a cada barra.

Finalmente, tomamos el más grande de todos. Aquí hay un análisis completo realizado por mí con un ejemplo.

Puede suscribirse a mi canal http://cb.lk/yt para obtener más tutoriales de este tipo.

Happy Coding 🙂

Puede referirse a esta respuesta: la respuesta de Pratik Moona a los Algoritmos: ¿Cuál es el enfoque algorítmico para resolver SPOJ.com – Problema CTGAME?

int maxRectangle (vector arr)
{
stack ss;
int maxArea = 0, i = 0; // lógica para manejar 0110
while (i if (ss.empty () || (arr [i] – ‘0’)> = (arr [ss.top ()] – ‘0’)) {
ss.push (i ++);
} más {
int top = ss.top ();
ss.pop ();
int diff = arr [arriba] – ‘0’;
maxArea = max (maxArea, (arr [top] – ‘0’) * (ss.empty ()? i: (i – (ss.top ()) – 1)));
// i ++;
}
}
while (! ss.empty ()) {// en caso de que el número termine con 1 o elementos hasta que encuentre 0
char top = ss.top ();
ss.pop ();
int diff = arr [arriba] – ‘0’; // da
int diff1 = ss.empty ()? i: (i – ss.top () – 1);
maxArea = max (maxArea, (diff) * (ss.empty ()? i: (i – ss.top () – 1)));
}
return maxArea;
}

return maxArea;
}

Consulte este enlace para problemas similares:
http://www.writeulearn.com/find- …

No sé mucho sobre esto, solo quiero intentarlo. Dado que los rectángulos en el histograma tienen tamaños de ancho similares pero solo diferentes alturas, entonces supongo que el algoritmo / programa debe escribirse en función de la altura.