Largest Rectangle in Histogram

Q: ¿Cuál es la complejidad temporal de «Largest Rectangle in Histogram»?

La solución con una pila monótona se ejecuta en tiempo O(n) y usa O(n) de espacio adicional. Cada índice se inserta una vez y se extrae una vez, y cada extracción requiere una cantidad constante de trabajo. Probar cada tramo de barras toma O(n²) de tiempo, aproximadamente 2 × 10^8 pasos para 2 × 10^4 barras.

DifícilPila monótona

+10

Un histograma es una fila de barras contiguas, sin espacios entre ellas, cada una de una unidad de ancho: heights[i] es la altura de la barra i. Un rectángulo dentro del histograma abarca un conjunto de barras vecinas y no puede ser más alto que la barra más baja de ese conjunto.

Devuelve el área más grande que puede tener un rectángulo de este tipo.

Función

largestRectangleArea(heights: integer-array) → integer

heightsinteger-array: la altura de cada barra, de izquierda a derecha
Devuelveinteger: el área del rectángulo más grande que cabe en el histograma

Restricciones

1 ≤ heights.length ≤ 2 × 10⁴
0 ≤ heights[i] ≤ 10⁵
Cada barra tiene una unidad de ancho, así que un rectángulo sobre las barras i a j tiene j-i+1 unidades de ancho.

Ejemplos

Entrada: heights = [2, 5, 6, 3, 4, 1]
Salida: 12
Explicación: Las cuatro barras 5, 6, 3 y 4 tienen todas una altura de al menos 3, así que un rectángulo de altura 3 las abarca: 3 × 4 = 12. Las dos barras más altas, 5 y 6, solo dan 5 × 2 = 10.

+17 pruebas ocultas al enviar

Para ir más allá

Supón que cada barra tiene su propio ancho, indicado en un segundo array. ¿Qué cambia en la solución de una sola pasada con pila?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Un rectángulo puede empezar y terminar en cualquier barra, y su altura depende de la barra más baja que cubre, así que probar cada tramo de barras cuesta aproximadamente n²/2 pasos. La solución es plantear la pregunta al revés: el mejor rectángulo tiene exactamente la altura de una de sus barras, así que cada barra solo necesita saber hasta dónde puede extenderse antes de que una barra más baja la detenga. Una pila monótona encuentra esos puntos de detención para cada barra, primero en dos pasadas y luego en una.

Prueba cada ejecución con un mínimo acumulado

Correcto, pero no termina con las pruebas más grandes

Intuición

Un rectángulo cubre una secuencia de barras contiguas desde start hasta end, y su altura está limitada por la barra más baja de la secuencia. Así que prueba todas las secuencias. Fija start, luego amplía end una barra a la vez y conserva la menor altura observada hasta el momento. El área del mejor rectángulo de esa secuencia es lowest × (end-start+1).

En [2, 5, 6, 3, 4, 1], empieza en el 5. Las secuencias dan 5 × 1 = 5, después 5 × 2 = 10 con el 6, luego 3 × 3 = 9 cuando se añade el 3, 3 × 4 = 12 con el 4, y 1 × 5 = 5 con el 1. El 12 es la respuesta. Actualizar lowest a medida que crece la secuencia mantiene cada paso en O(1), así que nunca vuelves a recorrer una secuencia para encontrar su mínimo.

Es correcto porque todo rectángulo se encuentra sobre alguna secuencia, y para una secuencia fija el rectángulo más alto que cabe tiene exactamente la altura de la barra más baja. Es lento porque hay n(n+1)/2 secuencias: alrededor de 2 × 10^8 para 2 × 10^4 barras, y esa cantidad no depende en absoluto de las alturas. La mayoría de esas secuencias se ven interrumpidas por una barra baja mucho antes de llegar al final, y la fuerza bruta las sigue extendiendo de todos modos.

Algoritmo

Establece best en 0.
Para cada start, establece lowest en heights[start].
Para cada end desde start hasta la última barra, reduce lowest a heights[end] si esa barra es más corta.
Actualiza best con lowest × (end-start+1).
Devuelve best.

def largestRectangleArea(heights):
    n = len(heights)
    best = 0
    for start in range(n):
        lowest = heights[start]
        for end in range(start, n):
            # The rectangle over start..end is as tall as the lowest bar in it.
            lowest = min(lowest, heights[end])
            best = max(best, lowest * (end - start + 1))
    return best

Barra más cercana y más corta a cada lado

Intuición

Invierte la búsqueda. En el mejor rectángulo, al menos una barra que hay debajo tiene exactamente la misma altura que el rectángulo; de lo contrario, podrías elevar el rectángulo. Así que la respuesta es el mejor rectángulo, entre todas las barras i, que tenga exactamente heights[i] de altura y se extienda lo más ancho posible. Se extiende hasta encontrarse con una barra estrictamente más baja a cada lado. Llama a sus índices left[i] y right[i], usando -1 y n cuando no haya ninguna. El rectángulo cubre las barras que están estrictamente entre ellas: ancho right[i]-left[i]-1. Eso son n candidatos en lugar de n²/2.

Para encontrar left[i] para cada barra, recorre de izquierda a derecha con una pila de índices cuyas alturas aumentan estrictamente de abajo arriba. Cuando llega la barra i, saca todos los índices cuyas barras tengan una altura igual o superior a heights[i]. Esas barras nunca podrán ser la barra más cercana más baja para i ni para ninguna barra posterior, porque i está más cerca y no es más alta. La que quede arriba será la barra más cercana más baja a la izquierda. Después, añade i a la pila. El mismo recorrido de derecha a izquierda proporciona right[i].

Para [2, 5, 6, 3, 4, 1], los recorridos dan left = [-1, 0, 1, 0, 3, -1] y right = [5, 3, 3, 5, 5, 6]. La barra de altura 3 en el índice 3 queda limitada por la de altura 2 en el índice 0 y la de altura 1 en el índice 5, así que su rectángulo es 3 × (5-0-1) = 12. La de altura 6 queda encajonada por sus vecinas y solo da 6 × 1.

Cada índice se añade una vez y se saca como máximo una vez en cada recorrido, así que ambos recorridos son O(n), aunque una barra pueda hacer que se saquen muchas otras. El coste son dos matrices adicionales.

Algoritmo

Recorre de izquierda a derecha con una pila vacía. Para cada i, saca elementos mientras la barra de la cima sea al menos tan alta como heights[i]; asigna a left[i] el elemento de la cima, o -1 si la pila está vacía; apila i.
Recorre de derecha a izquierda de la misma manera para llenar right[i], usando n si la pila está vacía.
Para cada i, calcula heights[i] × (right[i]-left[i]-1).
Devuelve la mayor de esas áreas.

def largestRectangleArea(heights):
    n = len(heights)
    left = [-1] * n  # index of the nearest shorter bar on the left, or -1
    right = [n] * n  # index of the nearest shorter bar on the right, or n
    stack = []  # indices whose heights rise strictly from bottom to top
    for i in range(n):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        if stack:
            left[i] = stack[-1]
        stack.append(i)
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        if stack:
            right[i] = stack[-1]
        stack.append(i)
    best = 0
    for i in range(n):
        # Bar i is the lowest bar of everything strictly between left[i] and right[i].
        best = max(best, heights[i] * (right[i] - left[i] - 1))
    return best

Una pasada con una pila monótona

Intuición

El recorrido de izquierda a derecha ya encuentra todos los límites derechos; los descarta. Cuando la barra i saca la barra t, heights[i] no es más alta que heights[t], así que i es donde termina por la derecha el rectángulo de t. Y el índice que queda debajo de t en la pila es donde termina por la izquierda. Así que mide el rectángulo en el momento de sacarlo: heights[t] × (i - below - 1), donde below es el nuevo tope de la pila, o -1 si la pila está vacía.

El invariante: las alturas de la pila aumentan estrictamente de abajo arriba, y el índice debajo de cada entrada es la barra más cercana a su izquierda que es más baja que ella. Todas las barras entre ambas fueron sacadas en el proceso, ya sea por la propia entrada o por una barra que la entrada sacó después, así que ninguna de ellas es más baja que la entrada. Las barras que nunca se sacan llegan hasta el final, así que después de procesar la última barra se procesa una barra más de altura 0. Es más baja que todas y vacía la pila.

Recorre [2, 5, 6, 3, 4, 1]. Apila 2, 5 y 6: la pila contiene los índices [0, 1, 2]. El 3 en el índice 3 saca el 6 (área 6 × (3-1-1) = 6) y el 5 (área 5 × (3-0-1) = 10), luego se detiene en el 2 y se apila. Apila el 4. El 1 en el índice 5 saca el 4 (área 4) y luego el 3, cuyo rectángulo va del índice 1 al 4: 3 × (5-0-1) = 12. También saca el 2 (2 × 5 = 10; la pila está vacía, así que el ancho es 5). El 0 de cierre saca el 1 (1 × 6 = 6). El máximo es 12.

Sacar con >= significa que una barra de igual altura puede detener una barra antes de tiempo. Eso es seguro: la barra de igual altura ocupa su lugar en la pila, hereda el mismo límite izquierdo y, cuando se saca más tarde, su rectángulo abarca toda la secuencia. En [3, 3, 3, 3], los primeros tres 3 registran anchos de 1, 2 y 3, y el último se saca con el 0 de cierre con ancho 4, dando 12.

Algoritmo

Empieza con una pila vacía de índices y best = 0.
Para i desde 0 hasta n, toma como altura actual heights[i], o 0 cuando i = n.
Mientras la barra en la cima de la pila sea al menos tan alta como la altura actual, sácala como t; el ancho es i - below - 1, donde below es la nueva cima o -1; actualiza best con heights[t] × width.
Apila i.
Devuelve best.

def largestRectangleArea(heights):
    n = len(heights)
    stack = []  # indices whose heights rise strictly from bottom to top
    best = 0
    for i in range(n + 1):
        current = heights[i] if i < n else 0  # a bar of 0 past the end empties the stack
        while stack and heights[stack[-1]] >= current:
            # Bar i stops the popped bar on the right; the bar below it stops it on the left.
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1
            best = max(best, height * (i - left - 1))
        stack.append(i)
    return best

Errores comunes y casos límite

El bucle de la pila es corto, y casi todos los errores están en el ancho o en las barras que quedan al final.

Olvidarse de las barras que siguen en la pila. En un histograma ascendente como [1, 2, 3, 4, 5], nunca se extrae nada dentro del bucle y, sin la barra de cierre de altura 0, se devuelve 0 en lugar de 9.
Medir el ancho desde el índice de la propia barra extraída. Su rectángulo empieza justo después de la barra que está debajo en la pila, no en la propia barra: en [2, 5, 6, 3, 4, 1], el 3 del índice 3 abarca los índices del 1 al 4. Usar i - t da 2 en lugar de 4.
Usar un ancho incorrecto cuando la pila está vacía después de una extracción. La barra extraída es la más baja hasta el momento, así que su rectángulo se extiende hasta el índice 0 y el ancho es i. En [2, 1, 2], el 1 abarca las tres barras, con un área de 3.
Detenerse ante barras iguales en ambos lados en la versión de dos pasadas. Entonces, en [3, 3, 3, 3], cada barra tiene un ancho de 1 y se devuelve 3 en lugar de 12. Extrae con >= para que los límites sean barras estrictamente más bajas.
Suponer que gana la barra más alta o el tramo más ancho. En [2, 5, 6, 3, 4, 1], ni el 6 ni el ancho completo de 6 barras dan la respuesta; la da una altura intermedia sobre un ancho intermedio.
Desbordamiento. Aquí, un área alcanza 10^5 × 2 × 10^4 = 2 × 10^9, lo que todavía cabe en un entero con signo de 32 bits; con límites mayores, multiplica en 64 bits.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de «Largest Rectangle in Histogram»?

La solución con una pila monótona se ejecuta en tiempo O(n) y usa O(n) de espacio adicional. Cada índice se inserta una vez y se extrae una vez, y cada extracción requiere una cantidad constante de trabajo. Probar cada tramo de barras toma O(n²) de tiempo, aproximadamente 2 × 10^8 pasos para 2 × 10^4 barras.

¿Por qué se mide el rectángulo de una barra cuando aparece?

Una barra se extrae cuando se encuentra la primera barra a su derecha que no es más alta, así que ahí es donde termina su rectángulo por la derecha. El índice que está debajo de ella en la pila corresponde a la barra más cercana a su izquierda que es más baja, así que ahí es donde termina por la izquierda. En el momento de extraerla, se conocen ambos extremos, y el área es height × (i - below - 1).

¿Se puede resolver el problema del rectángulo más grande en un histograma con divide y vencerás?

Sí. La barra más baja de todo el rango está debajo del mejor rectángulo, que entonces es lowest × width, o divide el rango en una parte izquierda y otra derecha que resuelves por separado. Con un recorrido lineal para encontrar el mínimo, esto es O(n log n) con una entrada aleatoria, pero O(n²) con una ordenada; un árbol de segmentos para mínimos de rango lo hace siempre O(n log n). La pila es más sencilla y rápida.

¿Cómo se usa el rectángulo más grande en un histograma para encontrar el rectángulo máximo en una cuadrícula de 0/1?

Recorre la cuadrícula fila por fila y lleva, para cada columna, la cantidad de 1 consecutivos que terminan en la fila actual; un 0 reinicia esa cuenta. Los conteos de cada fila forman un histograma, y el rectángulo más grande de 1 que termina en esa fila es el rectángulo más grande de ese histograma. Ejecutar la pila una vez por fila resuelve la cuadrícula en O(rows × cols) tiempo.

Python

def largestRectangleArea(heights):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

heights = [2, 5, 6, 3, 4, 1]

Esperado

Largest Rectangle in Histogram

Función

Restricciones

Ejemplos

Pistas

Solución

Prueba cada ejecución con un mínimo acumulado

Barra más cercana y más corta a cada lado

Una pasada con una pila monótona

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares