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 tiempo O(n) y usa O(1) de espacio adicional, ya que en cada paso mueve un puntero una posición hacia adentro. Comprobar cada par toma O(n²), y ordenar las líneas por altura toma O(n log n).

Q: ¿Por qué mover el puntero en 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 la otra más cerca, así que es más estrecho y no más alto. Ninguno puede superar al recipiente que mediste, 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 deshace: descartar la línea más corta. La decisión es segura porque cualquier recipiente que descarta no es mejor que uno que ya se ha medido, por eso el problema se clasifica tanto como voraz como de dos punteros.

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. Cualquier par de líneas forma un recipiente con el suelo, que 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 interfieren. 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, con alturas de 7 y 6, están separadas por 6 y contienen 6 × 6 = 36. Las dos líneas más altas, los 7 en las posiciones 1 y 5, contienen solo 7 × 4 = 28.

Para ir más allá

Aquí se ignoran las líneas que hay entre tus dos líneas. Si cada línea fuera una barra sólida, ¿cuánta agua se acumularía entre todas ellas? ¿Puedes calcularlo también en O(n)?

Solución

Comprobar todos los pares n²/2 implica 5 × 10^7 productos para 10^4 líneas. El agua depende únicamente de la línea más corta de cada par, así que, una vez que una línea es el lado más corto del recipiente más ancho que puede formar, ningún recipiente más estrecho que la use puede ofrecer un resultado mejor. Dos punteros convierten esto en un solo recorrido desde ambos extremos.

Comprueba cada par

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

Intuición

Un par i < j contiene min(height[i], height[j]) × (j - i): el agua se derrama por encima de la pared más baja, y el suelo tiene j - i de ancho. Prueba cada par y conserva el mayor.

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 n se duplica.

Algoritmo

Establece best en 0.
Para cada i y cada j que viene después, calcula min(height[i], height[j]) × (j - i).
Conserva el mayor 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

Si la línea i es el lado más corto de un recipiente, su pareja puede ser cualquier línea al menos igual de alta. Así que el mejor recipiente de este tipo la empareja con la línea más lejana que sea al menos igual de alta.

Ordena las líneas de la más alta a la más baja. Cuando le toca a la línea i, todas las líneas colocadas tienen al menos su altura, y la más lejana es el índice colocado más a la izquierda o más a la derecha, lo o hi. Así que la línea i puede contener como máximo height[i] × max(i - lo, hi - i), y el mejor recipiente se cuenta cuando le toca a su línea más corta. De dos líneas iguales, la segunda en colocarse ve a la primera como pareja.

En el primer ejemplo, los 7 de las posiciones 1 y 5 aparecen primero y contienen 28. Después, el 6 de la posición 7 ve lo = 1 y contiene 36. La ordenación cuesta O(n log n) de tiempo y O(n) de 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] multiplicado 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 supongamos que height[left] ≤ height[right]. Cualquier otro contenedor que use la línea left la empareja con una línea más cercana, así que es más estrecho y no supera la altura de 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. Si las alturas son iguales, ambas líneas quedan descartadas, así que da igual cuál muevas.

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

En el primer ejemplo, las posiciones 0 y 7 contienen 21 y se descarta el 3. Las posiciones 1 y 7 contienen 36 y se descarta el 6. Los valores restantes son 15, 28, 12, 10 y 2.

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 hacia la derecha. De lo contrario, mueve right un paso hacia 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

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 se va antes de 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.
Medir el ancho como j - i + 1. Las líneas en las posiciones i y j están separadas por j - i, así que [4, 4] contiene 4, no 8.
Suponer que la respuesta usa las líneas más altas o el par exterior. En el primer ejemplo, los dos 7 contienen 28 y el par exterior 21, mientras que la respuesta es 36.

Preguntas frecuentes3

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

La solución de dos punteros se ejecuta en tiempo O(n) y usa O(1) de espacio adicional, ya que en cada paso mueve un puntero una posición hacia adentro. Comprobar cada par toma O(n²), y ordenar las líneas por altura toma O(n log n).

¿Por qué mover el puntero en 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 la otra más cerca, así que es más estrecho y no más alto. Ninguno puede superar al recipiente que mediste, 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 deshace: descartar la línea más corta. La decisión es segura porque cualquier recipiente que descarta no es mejor que uno que ya se ha medido, por eso el problema se clasifica tanto como voraz como de dos punteros.

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

Prueba #1

Prueba #2

Argumento

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

Salida Esperada

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 frecuentes3

Problemas similares