Container With Most Water

Q: ¿Cuál es la complejidad temporal de Container With Most Water?

La solución de dos punteros se ejecuta en O(n) y usa O(1) de espacio adicional. En cada paso, se mueve un puntero una posición hacia el interior, por lo que hay como máximo n-1 pasos. Comprobar cada par toma O(n²), y ordenar las líneas por altura toma O(n log n).

Q: ¿Por qué mover el puntero a la línea más corta?

El agua queda limitada por la línea más corta. Cualquier otro recipiente que conserve esa línea tiene otra más cercana, así que es más estrecho y no más alto que la línea más corta. Ninguno puede superar el recipiente que has medido, así que puedes descartar la línea más corta sin perder la respuesta.

Q: ¿Es Container With Most Water un problema voraz?

Sí. Cada paso toma una decisión local que nunca se revierte: descarta la línea más corta. La decisión es segura porque todos los contenedores que el paso descarta no son mejores que uno que ya se midió. Por eso, el problema se clasifica tanto como voraz como de dos punteros.

Q: ¿En qué se diferencia Container With Most Water de Trapping Rain Water?

Aquí solo importan las dos líneas elegidas y se ignoran las líneas que hay entre ellas, así que la respuesta es un único rectángulo. En Trapping Rain Water, cada barra es sólida y el agua se acumula sobre cada barra hasta la altura de la más baja de las barras más altas a sus dos lados, así que la respuesta es una suma de todas las posiciones. Ambos problemas tienen soluciones con dos punteros de O(n), pero las reglas para mover los punteros y lo que se suma son distintos.

MedioDos punteros Voraz

+10

Recibes una lista height de enteros no negativos. La línea i es una pared vertical de altura height[i] situada en la posición i. Dos líneas cualesquiera forman un recipiente con el suelo, y este puede contener tanta agua como la altura de la línea más corta multiplicada por la distancia entre las dos líneas. Las demás líneas no estorban. Devuelve la máxima cantidad de agua que puede contener un solo par de líneas.

Función

maxArea(height: integer-array) → integer

heightinteger-array: las alturas de las líneas en las posiciones 0, 1, 2 y así sucesivamente
Devuelveinteger: la mayor cantidad de agua que pueden contener dos líneas

Restricciones

2 ≤ height.length ≤ 10⁴
0 ≤ height[i] ≤ 10⁴
La respuesta es como máximo 10⁸, así que cabe en un entero de 32 bits.

Ejemplos

Entrada: height = [3, 7, 2, 5, 4, 7, 3, 6]
Salida: 36
Explicación: Las líneas en las posiciones 1 y 7 tienen alturas de 7 y 6 y están separadas por 6, así que contienen 6 × 6 = 36. Las dos líneas más altas, los 7 en las posiciones 1 y 5, contienen solo 7 × 4 = 28, y el par exterior contiene 3 × 7 = 21.

+15 pruebas ocultas al enviar

Para ir más allá

Aquí se ignoran las líneas que están entre las dos que elijas. Si todas las líneas fueran barras sólidas, ¿cuánta agua se acumularía entre todas ellas? ¿Puedes calcularlo también en O(n)?

Solución

Hay alrededor de n²/2 pares de líneas, así que, para 10^4 líneas, comprobarlas todas implica 5 × 10^7 productos. La solución es que el agua depende solo de la línea más corta de cada par: una vez que sabes que una línea es el lado más corto del recipiente más ancho que aún puede formar, ningún recipiente más estrecho que la use puede ser mejor. Dos punteros convierten ese hecho en un solo recorrido desde ambos extremos.

Comprueba cada par

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

Intuición

Cada contenedor es un par de posiciones i < j. El agua sube hasta que se derrama por encima de la pared más baja, y el suelo entre las paredes tiene una anchura de j - i, así que el par contiene min(height[i], height[j]) × (j - i). Prueba todos los pares, conserva el mayor y tendrás la respuesta por definición.

El problema es la cantidad de pares. n líneas dan n(n-1)/2 pares: unos 5 × 10^7 para 10^4 líneas, y cuatro veces más cada vez que se duplica la lista. Un lenguaje compilado puede procesar esa cantidad en una fracción de segundo, pero Python, Ruby o R necesitan muchos segundos, y la cantidad crece demasiado rápido para cualquier lenguaje cuando n alcanza 10^5.

Algoritmo

Establece best en 0.
Para cada i, y cada j que le sigue, calcula min(height[i], height[j]) × (j - i).
Conserva el mayor valor entre best y ese valor.
Devuelve best.

def maxArea(height):
    n = len(height)
    best = 0
    for i in range(n):
        for j in range(i + 1, n):
            water = min(height[i], height[j]) * (j - i)
            best = max(best, water)
    return best

Las líneas más altas primero

Intuición

Observa un recipiente desde el lado de su línea más corta. Si la línea i es el lado más corto, el agua es height[i] multiplicado por la distancia, y la línea compañera puede ser cualquiera que tenga al menos la misma altura. Por tanto, el mejor recipiente en el que i es el lado más corto la empareja con la línea más alejada que tenga al menos la misma altura.

Para encontrar rápidamente esas líneas compañeras, ordena las líneas de la más alta a la más baja. Cuando le toque a la línea i, todas las líneas colocadas antes tienen al menos la misma altura, y la más alejada de ellas es el índice colocado más a la izquierda o más a la derecha. Lleva el seguimiento de esos dos índices, lo y hi, y la línea i puede contener como máximo height[i] × max(i - lo, hi - i). La respuesta es el mayor de estos valores, porque el mejor recipiente se cuenta cuando le toca a su línea más corta.

En el primer ejemplo, los dos 7 en las posiciones 1 y 5 aparecen primero y contienen 28. El 6 en la posición 7 aparece después, con lo = 1 y hi = 5, y contiene 6 × 6 = 36. Ninguna línea más baja supera ese valor. Las alturas iguales pueden aparecer en cualquier orden: la que aparezca en segundo lugar verá a la primera como una línea compañera.

La ordenación cuesta O(n log n) y el recorrido O(n), lo cual es lo bastante rápido. Aun así, requiere O(n) de memoria para el orden, y el siguiente enfoque elimina tanto la ordenación como la memoria.

Algoritmo

Ordena los índices por altura, del más alto al más bajo.
Establece lo y hi en el primer índice de ese orden y best en 0.
Para cada índice siguiente i, calcula height[i] por el mayor de i - lo y hi - i, y conserva el mejor valor.
Actualiza lo y hi para incluir i.
Devuelve best.

def maxArea(height):
    # Indices from the tallest line to the shortest.
    order = sorted(range(len(height)), key=lambda i: height[i], reverse=True)
    lo = hi = order[0]  # leftmost and rightmost index among the lines placed so far
    best = 0
    for i in order[1:]:
        # Every placed line is at least as tall as line i, so line i is the
        # shorter side, and its best partner is the placed line farthest away.
        best = max(best, height[i] * max(i - lo, hi - i))
        lo = min(lo, i)
        hi = max(hi, i)
    return best

Dos punteros desde ambos extremos

Intuición

Empieza con el contenedor más ancho, left = 0 y right = n-1, y mídelo. Ahora se puede descartar una de las dos líneas, y la elección es obligada: descarta la más corta. Supongamos que height[left] ≤ height[right]. Todos los demás contenedores que usan la línea left la emparejan con una línea más cercana que right, por lo que son más estrechos, y su altura sigue siendo como máximo height[left]. Ninguno contiene más agua que la que mediste, así que la línea left ya está descartada y left avanza un paso a la derecha. En cambio, mover la línea más alta mantendría el mismo límite para la altura y reduciría el ancho, así que solo puede empeorar el resultado. Cuando las dos alturas son iguales, ambas líneas ya están descartadas, y da igual cuál muevas.

Cada paso descarta definitivamente una línea, así que, después de n-1 pasos, los punteros se encuentran. Nunca se omite el mejor par: la primera vez que se descarta una de sus dos líneas, el contenedor medido en ese momento contiene al menos la misma cantidad de agua.

En [3, 7, 2, 5, 4, 7, 3, 6], las posiciones 0 y 7 contienen 3 × 7 = 21. El 3 es más corto, así que left avanza a 1. Las posiciones 1 y 7 contienen 6 × 6 = 36, y ahora el 6 es más corto, así que right retrocede a 6. Los contenedores siguientes contienen 15, 28, 12, 10 y 2, así que la respuesta sigue siendo 36.

Algoritmo

Establece left = 0, right = n-1 y best = 0.
Mientras left < right, calcula min(height[left], height[right]) × (right - left) y conserva el mejor valor.
Si height[left] < height[right], mueve left un paso a la derecha. De lo contrario, mueve right un paso a la izquierda.
Cuando los punteros se encuentren, devuelve best.

def maxArea(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        water = min(height[left], height[right]) * (right - left)
        best = max(best, water)
        # The shorter line cannot do better with any line closer in, so drop it.
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

Errores comunes y casos límite

El bucle de dos punteros es corto, así que los errores están en los detalles.

Mover la línea más alta. En el primer ejemplo, que devuelve 21 en lugar de 36: el 6 en la posición 7 es la línea más alta del primer par, así que se va antes de llegar a encontrarse con el 7 en la posición 1.
Usar la línea más alta, o el promedio de las dos, como altura. El agua se derrama por encima de la pared más baja, así que la altura es el mínimo.
Un error de desfase de una posición en la anchura. Las líneas en las posiciones i y j están separadas por j - i, no por j - i + 1, así que dos líneas contiguas contienen un volumen igual a su altura menor multiplicada por 1.
Suponer que la respuesta usa la línea más alta o el par de los extremos. En el primer ejemplo, los dos 7 contienen 28 y el par de los extremos 21, mientras que la respuesta es 36.
Desbordamiento con límites mayores. Aquí el agua se mantiene por debajo de 10^8, pero con alturas y longitudes cercanas a 10^5, el producto supera 2^31 y requiere un entero de 64 bits.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Container With Most Water?

La solución de dos punteros se ejecuta en O(n) y usa O(1) de espacio adicional. En cada paso, se mueve un puntero una posición hacia el interior, por lo que hay como máximo n-1 pasos. Comprobar cada par toma O(n²), y ordenar las líneas por altura toma O(n log n).

¿Por qué mover el puntero a la línea más corta?

El agua queda limitada por la línea más corta. Cualquier otro recipiente que conserve esa línea tiene otra más cercana, así que es más estrecho y no más alto que la línea más corta. Ninguno puede superar el recipiente que has medido, así que puedes descartar la línea más corta sin perder la respuesta.

¿Es Container With Most Water un problema voraz?

Sí. Cada paso toma una decisión local que nunca se revierte: descarta la línea más corta. La decisión es segura porque todos los contenedores que el paso descarta no son mejores que uno que ya se midió. Por eso, el problema se clasifica tanto como voraz como de dos punteros.

¿En qué se diferencia Container With Most Water de Trapping Rain Water?

Aquí solo importan las dos líneas elegidas y se ignoran las líneas que hay entre ellas, así que la respuesta es un único rectángulo. En Trapping Rain Water, cada barra es sólida y el agua se acumula sobre cada barra hasta la altura de la más baja de las barras más altas a sus dos lados, así que la respuesta es una suma de todas las posiciones. Ambos problemas tienen soluciones con dos punteros de O(n), pero las reglas para mover los punteros y lo que se suma son distintos.

Python

def maxArea(height):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Entrada

height = [3, 7, 2, 5, 4, 7, 3, 6]

Esperado

Container With Most Water

Función

Restricciones

Ejemplos

Pistas

Solución

Comprueba cada par

Las líneas más altas primero

Dos punteros desde ambos extremos

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares