Two Pointers

10. Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i-th line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Note: You may not slant the container.

Examples

Example 1

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The maximum area of water the container can store is 49.

Example 2

Input: height = [1,1]
Output: 1

Constraints

n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4

Se te da un arreglo de enteros height de longitud n. Hay n lineas verticales dibujadas de tal forma que los dos extremos de la linea i-esima son (i, 0) y (i, height[i]).

Encuentra dos lineas que, junto con el eje x, formen un contenedor que pueda almacenar la mayor cantidad de agua.

Devuelve la cantidad maxima de agua que el contenedor puede almacenar.

Nota: No puedes inclinar el contenedor.

Ejemplos

Ejemplo 1

Entrada: height = [1,8,6,2,5,4,8,3,7]
Salida: 49
Explicacion: El area maxima que puede almacenar el contenedor es 49.

Ejemplo 2

Entrada: height = [1,1]
Salida: 1

Restricciones

n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4

conteiner_most_water.py

from typing import List

# Two-pointer approach to find the container that holds the most water
height: List[int] = [1, 3, 7, 5, 3, 2, 6, 9, 1]
max_area: int = 0
l, r = 0, len(height) - 1

while l < r:
    area: int = min(height[l], height[r]) * (r - l)
    max_area = max(max_area, area)

    if height[l] < height[r]:
        l += 1
    else:
        r -= 1

print(max_area)

Keyboard shortcuts

← h Previous problem

→ l Next problem

Esc Back to index

? Toggle this help