Container With Most Water

Q: Quelle est la complexité temporelle de Container With Most Water ?

La solution à deux pointeurs s’exécute en O(n) et utilise O(1) d’espace supplémentaire, car à chaque étape, un pointeur avance d’une position vers l’intérieur. Vérifier chaque paire prend O(n²), et trier les lignes par hauteur prend O(n log n).

Q: Pourquoi déplacer le pointeur vers la ligne la plus courte ?

L’eau est limitée par la ligne la plus courte. Tout autre récipient qui utilise cette ligne a une autre ligne plus proche, donc il est moins large et pas plus haut. Aucun d’eux ne peut contenir plus d’eau que le récipient que tu as mesuré, donc la ligne la plus courte peut être écartée sans perdre la réponse.

Q: Le problème « Container With Most Water » est-il un problème glouton ?

Oui. À chaque étape, on fait un choix local qui n’est jamais annulé : éliminer la ligne la plus courte. Ce choix est sûr, car aucun des conteneurs qu’il écarte n’est meilleur qu’un conteneur déjà mesuré ; c’est pourquoi le problème est classé à la fois parmi les algorithmes gloutons et les problèmes à deux pointeurs.

MoyenDeux pointeurs Glouton

+10

On vous donne une liste height d’entiers non négatifs. La ligne i est un mur vertical de hauteur height[i] situé à la position i. Deux lignes quelconques forment un récipient avec le sol, qui peut contenir une quantité d’eau égale à la hauteur de la ligne la plus courte multipliée par la distance entre les deux lignes. Les autres lignes ne gênent pas. Renvoyez la quantité maximale d’eau qu’une seule paire de lignes peut contenir.

Fonction

maxArea(height: integer-array) → integer

heightinteger-array: les hauteurs des lignes aux positions 0, 1, 2, etc.
Renvoieinteger: la quantité maximale d’eau que deux lignes peuvent contenir

Contraintes

2 ≤ height.length ≤ 10⁴
0 ≤ height[i] ≤ 10⁴
La réponse est au plus égale à 10⁸, elle tient donc dans un entier de 32 bits.

Exemples

Entrée: height = [3, 7, 2, 5, 4, 7, 3, 6]
Sortie: 36
Explication: Les lignes aux positions 1 et 7, de hauteurs 7 et 6, sont distantes de 6 et peuvent contenir 6 × 6 = 36. Les deux lignes les plus hautes, les 7 aux positions 1 et 5, peuvent contenir seulement 7 × 4 = 28.

Pour aller plus loin

Ici, les lignes situées entre les deux tiennes sont ignorées. Si chaque ligne était une barre pleine, quelle quantité d’eau s’accumulerait entre elles toutes ? Peux-tu aussi calculer cela en O(n) ?

Solution

Vérifier toutes les paires n²/2 signifie effectuer 5 × 10^7 produits pour 10^4 lignes. La quantité d’eau dépend uniquement de la ligne la plus courte d’une paire, donc, dès qu’une ligne est le côté le plus court du conteneur le plus large qu’elle peut encore former, aucun conteneur plus étroit qui l’utilise ne peut faire mieux. Deux pointeurs permettent de parcourir le tableau une seule fois, depuis les deux extrémités.

Vérifiez chaque paire

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Une paire i < j correspond à min(height[i], height[j]) × (j - i) : l’eau déborde par le mur le plus bas, et le fond mesure j - i de large. Essaie toutes les paires et conserve la plus grande valeur.

n lignes donnent n(n-1)/2 paires : environ 5 × 10^7 pour 10^4 lignes, et quatre fois plus à chaque fois que n double.

Algorithme

Définis best à 0.
Pour chaque i, et chaque j après lui, calcule min(height[i], height[j]) × (j - i).
Conserve la plus grande valeur entre best et cette valeur.
Retourne 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

Les lignes les plus hautes d’abord

Intuition

Si la ligne i est le côté le plus court d’un récipient, son partenaire peut être n’importe quelle ligne au moins aussi haute. Le meilleur récipient de ce type l’associe donc à la ligne la plus éloignée qui soit au moins aussi haute.

Place les lignes de la plus haute à la plus courte. Lorsque la ligne i arrive, toutes les lignes déjà placées sont au moins aussi hautes, et la plus éloignée est l’indice placé le plus à gauche ou le plus à droite, lo ou hi. La ligne i peut donc contenir au mieux height[i] × max(i - lo, hi - i), et le meilleur récipient est comptabilisé lorsque son côté le plus court arrive. Parmi deux lignes de même hauteur, la seconde placée voit la première comme partenaire.

Dans le premier exemple, les 7 aux positions 1 et 5 arrivent en premier et contiennent 28. Le 6 à la position 7 voit alors lo = 1 et contient 36. Le tri nécessite un temps O(n log n) et une mémoire O(n).

Algorithme

Triez les indices par hauteur, du plus grand au plus petit.
Définissez lo et hi sur le premier indice de cet ordre, et best sur 0.
Pour chaque indice suivant i, calculez height[i] multiplié par la plus grande valeur entre i - lo et hi - i, et conservez la meilleure valeur.
Mettez à jour lo et hi pour inclure i.
Retournez 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

Deux pointeurs depuis les deux extrémités

Intuition

Commence avec le conteneur le plus large, left = 0 et right = n-1, et supposons que height[left] ≤ height[right]. Tous les autres conteneurs qui utilisent la ligne left l’associent à une ligne plus proche : ils sont donc plus étroits et pas plus hauts que height[left]. Aucun ne contient plus d’eau que celle que tu as mesurée, donc la ligne left est éliminée et left avance d’un pas vers la droite. Si les hauteurs sont égales, les deux lignes sont éliminées : tu peux donc déplacer l’un ou l’autre pointeur.

À chaque étape, une ligne est éliminée, donc les pointeurs se rejoignent après n-1 étapes. La meilleure paire n’est jamais ignorée : lorsque la première de ses deux lignes est éliminée, le conteneur mesuré à cet instant contient au moins autant d’eau.

Dans le premier exemple, les positions 0 et 7 contiennent 21, et le 3 est éliminé. Les positions 1 et 7 contiennent 36, et le 6 est éliminé. Les conteneurs restants contiennent 15, 28, 12, 10 et 2.

Algorithme

Définissez left = 0, right = n-1 et best = 0.
Tant que left < right, calculez min(height[left], height[right]) × (right - left) et conservez la meilleure valeur.
Si height[left] < height[right], déplacez left d’un pas vers la droite. Sinon, déplacez right d’un pas vers la gauche.
Lorsque les pointeurs se rencontrent, renvoyez 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

Pièges et cas limites

Déplacer la ligne la plus haute. Dans le premier exemple, le résultat est 21 au lieu de 36 : le 6 à la position 7 part avant même de rencontrer le 7 à la position 1.
Utiliser la ligne la plus haute, ou la moyenne des deux, comme hauteur. L’eau déborde par-dessus le mur le plus bas, donc la hauteur est le minimum.
Mesurer la largeur avec j - i + 1. Les lignes aux positions i et j sont séparées de j - i, donc [4, 4] contient 4, pas 8.
Supposer que la réponse utilise les lignes les plus hautes ou la paire extérieure. Dans le premier exemple, les deux 7 contiennent 28 et la paire extérieure 21, tandis que la réponse est 36.

Questions fréquentes3

Quelle est la complexité temporelle de Container With Most Water ?

La solution à deux pointeurs s’exécute en O(n) et utilise O(1) d’espace supplémentaire, car à chaque étape, un pointeur avance d’une position vers l’intérieur. Vérifier chaque paire prend O(n²), et trier les lignes par hauteur prend O(n log n).

Pourquoi déplacer le pointeur vers la ligne la plus courte ?

L’eau est limitée par la ligne la plus courte. Tout autre récipient qui utilise cette ligne a une autre ligne plus proche, donc il est moins large et pas plus haut. Aucun d’eux ne peut contenir plus d’eau que le récipient que tu as mesuré, donc la ligne la plus courte peut être écartée sans perdre la réponse.

Le problème « Container With Most Water » est-il un problème glouton ?

Oui. À chaque étape, on fait un choix local qui n’est jamais annulé : éliminer la ligne la plus courte. Ce choix est sûr, car aucun des conteneurs qu’il écarte n’est meilleur qu’un conteneur déjà mesuré ; c’est pourquoi le problème est classé à la fois parmi les algorithmes gloutons et les problèmes à deux pointeurs.

def maxArea(height):
    # Écrivez le code ici

Test #1

Test #2

Argument

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

Résultat attendu

Container With Most Water

Fonction

Contraintes

Exemples

Indices

Solution

Vérifiez chaque paire

Les lignes les plus hautes d’abord

Deux pointeurs depuis les deux extrémités

Pièges et cas limites

Questions fréquentes3

Problèmes similaires