algorithm - poligono - para que sirve un histograma

Maximiza el área rectangular bajo histograma

Question

Tengo un histograma con alturas enteras y ancho constante 1. Quiero maximizar el área rectangular bajo un histograma. p.ej:

 _
| |
| |_
| |
| |_
| |

La respuesta para esto sería 6, 3 * 2, usando col1 y col2.

O (n ^ 2) la fuerza bruta es clara para mí, me gustaría un algoritmo O (n log n). Estoy tratando de pensar la programación dinámica en la línea de máxima ascendencia creciente O (n log n) algo, pero no voy hacia adelante. ¿Debería usar el algoritmo de dividir y conquistar?

PD: a las personas con suficiente reputación se les pide que eliminen la etiqueta de dividir y vencer si no hay tal solución.

Después de los comentarios de mho: me refiero al área del rectángulo más grande que cabe por completo. (Gracias j_random_hacker por aclarar :)).

Answer 1

Codifiqué este y me sentí un poco mejor en el sentido:

import java.util.Stack;
class StackItem{
public int sup;
public int height;
public int sub;
public StackItem(int a, int b, int c){
sup = a;
height = b;
sub =c;
}
public int getArea(){
return (sup - sub)* height;
}
@Override
public String toString(){
return " from:"+sup+
" to:"+sub+
" height:"+height+
" Area ="+getArea();
}
}
public class MaxRectangleInHistogram {
Stack<StackItem> S;
StackItem curr;
StackItem maxRectangle;
public StackItem getMaxRectangleInHistogram(int A[], int n){
int i = 0;
S = new Stack();
S.push(new StackItem(0,0,-1));
maxRectangle = new StackItem(0,0,-1);
while(i<n){
curr = new StackItem(i,A[i],i);
if(curr.height > S.peek().height){
S.push(curr);
}else if(curr.height == S.peek().height){
S.peek().sup = i+1;
}else if(curr.height < S.peek().height){
while((S.size()>1) && (curr.height<=S.peek().height)){
curr.sub = S.peek().sub;
S.peek().sup = i;
decideMaxRectangle(S.peek());
S.pop();
}
S.push(curr);
}
i++;
}
while(S.size()>1){
S.peek().sup = i;
decideMaxRectangle(S.peek());
S.pop();
}
return maxRectangle;
}
private void decideMaxRectangle(StackItem s){
if(s.getArea() > maxRectangle.getArea() )
maxRectangle = s;
}
}

Solo nota:

Time Complexity: T(n) < O(2n) ~ O(n)
Space Complexity S(n) < O(n)

Answer 2

Hay tres formas de resolver este problema además del enfoque de fuerza bruta. Escribiré todos. Los códigos java han pasado las pruebas en un sitio de jueces en línea llamado leetcode: http://www.leetcode.com/onlinejudge#question_84 . así que estoy seguro de que los códigos son correctos.

Solución 1: programación dinámica + n * n matriz como caché

tiempo: O (n ^ 2), espacio: O (n ^ 2)

Idea básica: utilice la matriz n * n dp [i] [j] para almacenar en caché la altura mínima entre la barra [i] y la barra [j]. Comience a llenar la matriz de rectángulos de ancho 1.

public int solution1(int[] height) {
int n = height.length;
if(n == 0) return 0;
int[][] dp = new int[n][n];
int max = Integer.MIN_VALUE;
for(int width = 1; width <= n; width++){
for(int l = 0; l+width-1 < n; l++){
int r = l + width - 1;
if(width == 1){
dp[l][l] = height[l];
max = Math.max(max, dp[l][l]);
} else {
dp[l][r] = Math.min(dp[l][r-1], height[r]);
max = Math.max(max, dp[l][r] * width);
}
}
}
return max;
}

Solución 2: programación dinámica + 2 matrices como caché .

tiempo: O (n ^ 2), espacio: O (n)

Idea básica: esta solución es como la solución 1, pero ahorra espacio. La idea es que en la solución 1 construyamos la matriz desde la fila 1 hasta la fila n. Pero en cada iteración, solo la fila anterior contribuye a la construcción de la fila actual. Entonces, utilizamos dos matrices como fila previa y fila actual por turnos.

public int Solution2(int[] height) {
int n = height.length;
if(n == 0) return 0;
int max = Integer.MIN_VALUE;
// dp[0] and dp[1] take turns to be the "previous" line.
int[][] dp = new int[2][n];
for(int width = 1; width <= n; width++){
for(int l = 0; l+width-1 < n; l++){
if(width == 1){
dp[width%2][l] = height[l];
} else {
dp[width%2][l] = Math.min(dp[1-width%2][l], height[l+width-1]);
}
max = Math.max(max, dp[width%2][l] * width);
}
}
return max;
}

Solución 3: use la pila .

tiempo: O (n), espacio: O (n)

Esta solución es engañosa y aprendí cómo hacer esto a partir de la explicación sin gráficos ni explicación con gráficos . Le sugiero que lea los dos enlaces antes de leer mi explicación a continuación. Es difícil de explicar sin gráficos, por lo que mis explicaciones pueden ser difíciles de seguir.

Las siguientes son mis explicaciones:

1. Para cada barra, debemos ser capaces de encontrar el rectángulo más grande que contiene esta barra. Entonces, el más grande de estos n rectángulos es lo que queremos.

2. Para obtener el rectángulo más grande para una cierta barra (digamos bar [i], la (i + 1) barra th), solo tenemos que averiguar el intervalo más grande que contiene esta barra. Lo que sabemos es que todas las barras en este intervalo deben tener al menos la misma altura con la barra [i]. Entonces, si descubrimos cuántas barras consecutivas de la misma altura o más están a la izquierda de la barra [i], y cuántas barras consecutivas de la misma altura o más están a la derecha inmediata de la barra [ i], sabremos la longitud del intervalo, que es el ancho del rectángulo más grande para la barra [i].

3. Para contar el número de barras consecutivas con la misma altura o más alto en el extremo izquierdo de la barra [i], solo necesitamos encontrar la barra más cercana a la izquierda que es más corta que la barra [i], porque todas las barras entre esta barra y barra [i] serán barras consecutivas de altura igual o superior.

4. Usamos una pila para realizar un seguimiento dinámico de todas las barras de la izquierda que son más cortas que una cierta barra. En otras palabras, si iteramos desde la primera barra a la barra [i], cuando acabamos de llegar a la barra [i] y no hemos actualizado la pila, la pila debe almacenar todas las barras que no son más altas que la barra [i -1], incluida la barra [i-1] en sí. Comparamos la altura de bar [i] con cada barra de la pila hasta que encontramos una que es más corta que la barra [i], que es la barra más corta. Si la barra [i] es más alta que todas las barras en la pila, significa que todas las barras a la izquierda de la barra [i] son ​​más altas que la barra [i].

5. Podemos hacer lo mismo en el lado derecho de la barra i-th. Entonces sabemos para la barra [i] cuántas barras hay en el intervalo.

   public int solution3(int[] height) {
   int n = height.length;
   if(n == 0) return 0;
   Stack<Integer> left = new Stack<Integer>();
   Stack<Integer> right = new Stack<Integer>();
   int[] width = new int[n];// widths of intervals.
   Arrays.fill(width, 1);// all intervals should at least be 1 unit wide.
   for(int i = 0; i < n; i++){
   // count # of consecutive higher bars on the left of the (i+1)th bar
   while(!left.isEmpty() && height[i] <= height[left.peek()]){
   // while there are bars stored in the stack, we check the bar on the top of the stack.
   left.pop();
   }
   if(left.isEmpty()){
   // all elements on the left are larger than height[i].
   width[i] += i;
   } else {
   // bar[left.peek()] is the closest shorter bar.
   width[i] += i - left.peek() - 1;
   }
   left.push(i);
   }
   for (int i = n-1; i >=0; i--) {
   while(!right.isEmpty() && height[i] <= height[right.peek()]){
   right.pop();
   }
   if(right.isEmpty()){
   // all elements to the right are larger than height[i]
   width[i] += n - 1 - i;
   } else {
   width[i] += right.peek() - i - 1;
   }
   right.push(i);
   }
   int max = Integer.MIN_VALUE;
   for(int i = 0; i < n; i++){
   // find the maximum value of all rectangle areas.
   max = Math.max(max, width[i] * height[i]);
   }
   return max;
   }

Answer 3

Implementación en Python de la solución O (n) de respuesta de @ IVlad :

from collections import namedtuple
Info = namedtuple(''Info'', ''start height'')
def max_rectangle_area(histogram):
"""Find the area of the largest rectangle that fits entirely under
the histogram.
"""
stack = []
top = lambda: stack[-1]
max_area = 0
pos = 0 # current position in the histogram
for pos, height in enumerate(histogram):
start = pos # position where rectangle starts
while True:
if not stack or height > top().height:
stack.append(Info(start, height)) # push
elif stack and height < top().height:
max_area = max(max_area, top().height*(pos-top().start))
start, _ = stack.pop()
continue
break # height == top().height goes here
pos += 1
for start, height in stack:
max_area = max(max_area, height*(pos-start))
return max_area

Ejemplo:

>>> f = max_rectangle_area
>>> f([5,3,1])
6
>>> f([1,3,5])
6
>>> f([3,1,5])
5
>>> f([4,8,3,2,0])
9
>>> f([4,8,3,1,1,0])
9

Búsqueda lineal utilizando una pila de subproblemas incompletos

Copiar y pegar la descripción del algoritmo (en caso de que la página se caiga):

Procesamos los elementos en orden de izquierda a derecha y mantenemos una pila de información sobre los subhistogramas iniciados pero aún no finalizados. Cada vez que llega un nuevo elemento, está sujeto a las siguientes reglas. Si la pila está vacía, abrimos un nuevo subproblema presionando el elemento en la pila. De lo contrario, lo comparamos con el elemento en la parte superior de la pila. Si el nuevo es mayor, nuevamente lo presionamos. Si el nuevo es igual lo salteamos. En todos estos casos, continuamos con el siguiente elemento nuevo. Si el nuevo es menor, terminamos el subproblema superior al actualizar el área máxima del elemento en la parte superior de la pila. Luego, descartamos el elemento en la parte superior y repetimos el procedimiento manteniendo el nuevo elemento actual. De esta forma, todos los subproblemas se terminan hasta que la pila se vacía, o su elemento superior es menor o igual que el nuevo elemento, lo que lleva a las acciones descritas anteriormente. Si todos los elementos se han procesado y la pila aún no está vacía, finalizamos los subproblemas restantes actualizando el área máxima wrt a los elementos en la parte superior.

Para la actualización de un elemento, encontramos el rectángulo más grande que incluye ese elemento. Observe que se lleva a cabo una actualización del área máxima para todos los elementos, excepto los omitidos. Sin embargo, si se omite un elemento, tiene el mismo rectángulo más grande que el elemento en la parte superior de la pila en ese momento, que se actualizará más tarde. La altura del rectángulo más grande es, por supuesto, el valor del elemento. En el momento de la actualización, sabemos cuán lejos se extiende el rectángulo más grande a la derecha del elemento, porque entonces, por primera vez, llegó un nuevo elemento con una altura más pequeña. La información, qué tan lejos se extiende el rectángulo más grande a la izquierda del elemento, está disponible si también lo almacenamos en la pila.

Por lo tanto, revisamos el procedimiento descrito anteriormente. Si se empuja un elemento nuevo inmediatamente, ya sea porque la pila está vacía o es mayor que el elemento superior de la pila, el rectángulo más grande que lo contiene se extiende hacia la izquierda no más allá del elemento actual. Si se presiona después de que varios elementos se hayan quitado de la pila, porque es menor que estos elementos, el rectángulo más grande que lo contiene se extiende hacia la izquierda hasta el elemento más reciente.

Cada elemento se empuja y aparece a lo sumo una vez y en cada paso del procedimiento, al menos un elemento es empujado o reventado. Como la cantidad de trabajo para las decisiones y la actualización es constante, la complejidad del algoritmo es O (n) mediante análisis amortizado.

Answer 4

La solución de pila es una de las soluciones más inteligentes que he visto hasta la fecha. Y puede ser un poco difícil de entender por qué eso funciona.

He tomado un golpe para explicar lo mismo con cierto detalle aquí .

Puntos de resumen de la publicación: -

• La forma general en que nuestro cerebro piensa es:
  • Crea cada situación y trata de encontrar el valor del contraint que se necesita para resolver el problema.
  • Y felizmente lo convertimos en código como: - encuentre el valor de contraint (min) para cada situación (pair (i, j))

Las soluciones inteligentes intentan cambiar el problema. Para cada valor de constraint/min de esa área, ¿cuáles son los mejores extremos izquierdos y derechos posibles?

• Entonces si cruzamos sobre cada min posible en la matriz. ¿Cuáles son los extremos izquierdo y derecho para cada valor?

  • Poco pensamiento dice, el primer valor más a la izquierda menos que el current min y, de manera similar, el primer valor más a la derecha que es menor que el mínimo actual.

• Entonces ahora necesitamos ver si podemos encontrar una forma inteligente de encontrar los primeros valores izquierdos y derechos menores que el valor actual.

• Pensar : si hemos recorrido la matriz, digamos parcialmente hasta min_i, ¿cómo se puede construir la solución a min_i + 1?

• Necesitamos el primer valor menor que min_i a su izquierda.

• Invertir la instrucción: necesitamos ignorar todos los valores a la izquierda de min_i que sean mayores que min_i. Nos detenemos cuando encontramos el primer valor más pequeño que min_i (i). Las depresiones en la curva se vuelven inútiles una vez que las hemos cruzado . En el histograma, (2 4 3) => si 3 es min_i, 4 es mayor y no es de interés.
• Corrallar : en un rango (i, j). j es el valor mínimo que estamos considerando ... todos los valores entre j y su valor izquierdo i son inútiles. Incluso para más cálculos.
• Cualquier histograma a la derecha con un valor mínimo mayor que j, se vinculará en j. Los valores de interés a la izquierda forman una secuencia monótonamente creciente con j siendo el valor más grande. (Los valores de interés aquí son valores posibles que pueden ser de interés para la matriz posterior)
• Dado que, estamos viajando de izquierda a derecha, para cada valor mínimo / valor actual, no sabemos si el lado derecho de la matriz tendrá un elemento más pequeño que él.
  • Entonces, debemos mantenerlo en la memoria hasta que sepamos que este valor es inútil. (dado que se encuentra un valor menor)

• Todo esto conduce a un uso de nuestra propia estructura de stack .

  • Seguimos en la pila hasta que no sabemos que es inútil.
  • Eliminamos de la pila una vez que sabemos que la cosa es basura.

• Entonces, para que cada valor mínimo encuentre su valor más pequeño, hacemos lo siguiente:

  1. mostrar los elementos más grandes (valores inútiles)
  2. El primer elemento más pequeño que el valor es el extremo izquierdo. El yo a nuestro min.
• Podemos hacer lo mismo desde el lado derecho de la matriz y obtendremos j a nuestro min.

Es bastante difícil explicar esto, pero si esto tiene sentido, le sugiero que lea el artículo completo aquí ya que tiene más información y detalles.

Answer 5

La solución más fácil en O (N)

long long getMaxArea(long long hist[], long long n)
{
stack<long long> s;
long long max_area = 0;
long long tp;
long long area_with_top;
long long i = 0;
while (i < n)
{
if (s.empty() || hist[s.top()] <= hist[i])
s.push(i++);
else
{
tp = s.top(); // store the top index
s.pop(); // pop the top
area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);
if (max_area < area_with_top)
{
max_area = area_with_top;
}
}
}
while (!s.empty())
{
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;
}

Answer 6

Las respuestas anteriores han dado la mejor solución de O (n) en el código, sin embargo, sus explicaciones son bastante difíciles de comprender. El algoritmo O (n) usando una pila me pareció mágico al principio, pero ahora tiene todo el sentido para mí. OK, déjame explicarte.

Primera observación:

Para encontrar el rectángulo máximo, si para cada barra x , conocemos la primera barra más pequeña en cada lado, digamos l y r , estamos seguros de que la height[x] * (r - l - 1) es la mejor toma que puede obtener usando la altura de la barra x . En la figura a continuación, 1 y 2 son los primeros más pequeños de 5.

De acuerdo, supongamos que podemos hacer esto en O (1) vez para cada barra, ¡entonces podemos resolver este problema en O (n)! escaneando cada barra.

Entonces, surge la pregunta: para cada barra, ¿podemos realmente encontrar la primera barra más pequeña a la izquierda y a la derecha en O (1) vez? Eso parece imposible ¿no? ... Es posible, al usar una pila creciente.

¿Por qué usar una pila creciente puede hacer un seguimiento de los primeros más pequeños a la izquierda y a la derecha?

Tal vez si te digo que una pila creciente puede hacer el trabajo no es nada convincente, así que te guiaré en esto.

En primer lugar, para mantener la pila aumentando, necesitamos una operación:

while x < stack.top():
stack.pop()
stack.push(x)

Luego puedes verificar que en la pila creciente (como se muestra abajo), para la stack[x] , la stack[x-1] es la primera más pequeña a la izquierda, luego un nuevo elemento que puede sacar la stack[x] es la primera más pequeño a su derecha.

Todavía no puedo creer que la pila [x-1] sea la primera más pequeña a la izquierda en la pila [x]?

Lo probaré por contradicción.

En primer lugar, stack[x-1] < stack[x] es seguro. Pero supongamos que la stack[x-1] no es la primera más pequeña a la izquierda de la stack[x] .

Entonces, ¿dónde está el primer fs más pequeño?

If fs < stack[x-1]:
stack[x-1] will be popped out by fs,
else fs >= stack[x-1]:
fs shall be pushed into stack,
Either case will result fs lie between stack[x-1] and stack[x], which is contradicting to the fact that there is no item between stack[x-1] and stack[x].

Por lo tanto, la pila [x-1] debe ser la primera más pequeña.

Resumen:

El aumento de la pila puede hacer un seguimiento de la primera más pequeña a la izquierda y a la derecha para cada elemento. Al usar esta propiedad, el rectángulo máximo en el histograma se puede resolver usando una pila en O (n).

¡Felicitaciones! Este es realmente un problema difícil, me alegro de que mi explicación prosaica no te haya impedido terminar. Adjunto está mi solución probada como tu recompensa :)

def largestRectangleArea(A):
ans = 0
A = [-1] + A
A.append(-1)
n = len(A)
stack = [0] # store index
for i in range(n):
while A[i] < A[stack[-1]]:
h = A[stack.pop()]
area = h*(i-stack[-1]-1)
ans = max(ans, area)
stack.append(i)
return ans

Answer 7

No entiendo las otras entradas, pero creo que sé cómo hacerlo en O (n) de la siguiente manera.

A) para cada índice, encuentre el rectángulo más grande dentro del histograma que termina en ese índice donde la columna del índice toca la parte superior del rectángulo y recuerda dónde comienza el rectángulo. Esto se puede hacer en O (n) usando un algoritmo basado en pila.

B) De forma similar para cada índice, encuentre el rectángulo más grande que comience en ese índice donde la columna de índice toca la parte superior del rectángulo y recuerde dónde termina el rectángulo. También O (n) usando el mismo método que (A) pero escaneando el histograma hacia atrás.

C) Para cada índice combine los resultados de (A) y (B) para determinar el rectángulo más grande donde la columna en ese índice toca la parte superior del rectángulo. O (n) como (A).

D) Como el rectángulo más grande debe ser tocado por alguna columna del histograma, el rectángulo más grande es el rectángulo más grande que se encuentra en el paso (C).

La parte difícil es la implementación (A) y (B), que creo que es lo que JF Sebastian pudo haber resuelto más que el problema general planteado.

Answer 8

Puede usar el método O (n) que usa la pila para calcular el área máxima bajo el histograma.

long long histogramArea(vector<int> &histo){
stack<int> s;
long long maxArea=0;
long long area= 0;
int i =0;
for (i = 0; i < histo.size();) {
if(s.empty() || histo[s.top()] <= histo[i]){
s.push(i++);
}
else{
int top = s.top(); s.pop();
area= histo[top]* (s.empty()?i:i-s.top()-1);
if(area >maxArea)
maxArea= area;
}
}
while(!s.empty()){
int top = s.top();s.pop();
area= histo[top]* (s.empty()?i:i-s.top()-1);
if(area >maxArea)
maxArea= area;
}
return maxArea;
}

Para una explicación, puede leer aquí http://www.geeksforgeeks.org/largest-rectangle-under-histogram/

Answer 9

También hay otra solución usando Divide and Conquer. El algoritmo para esto es:

1) Divida la matriz en 2 partes con la menor altura como punto de ruptura

2) El área máxima es el máximo de: a) La menor altura * el tamaño de la matriz b) El rectángulo máximo en la mitad izquierda del array c) El rectángulo máximo en la mitad derecha del array

La complejidad del tiempo viene a O (nlogn)