Container With Most Water

Q: Quelle est la complexité temporelle du problème du récipient contenant le plus d’eau ?

La solution à deux pointeurs s’exécute en O(n) et utilise O(1) espace supplémentaire. À chaque étape, un pointeur avance d’une position vers l’intérieur, donc il y a au plus n-1 étapes. 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 conserve cette ligne a un partenaire plus proche, donc il est plus étroit et n’est toujours pas plus haut que la ligne la plus courte. Aucun d’eux ne peut faire mieux que le récipient que tu as mesuré, donc tu peux écarter la ligne la plus courte sans perdre la réponse.

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

Oui. À chaque étape, un choix local est effectué et n’est jamais annulé : la ligne la plus courte est écartée. Ce choix est sûr, car chaque conteneur éliminé à cette étape n’est pas meilleur que ceux déjà mesurés. C’est pourquoi ce problème relève à la fois des algorithmes gloutons et de la technique des deux pointeurs.

Q: En quoi le problème du récipient contenant le plus d’eau diffère-t-il de celui du piégeage de l’eau de pluie ?

Ici, seules les deux lignes choisies comptent et les lignes situées entre elles sont ignorées : la réponse est donc un seul rectangle. Dans Trapping Rain Water, chaque barre est pleine et l’eau s’accumule au-dessus de chaque barre jusqu’à la hauteur de la plus basse des barres les plus hautes situées de chaque côté ; la réponse est donc une somme sur toutes les positions. Les deux problèmes ont des solutions à deux pointeurs en O(n), mais les règles de déplacement des pointeurs et les éléments à additionner diffèrent.

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, et ainsi de suite
Renvoieinteger: la quantité d’eau maximale 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 ont des hauteurs de 7 et 6 et sont séparées de 6 unités ; elles contiennent donc 6 × 6 = 36. Les deux lignes les plus hautes, les 7 aux positions 1 et 5, ne contiennent que 7 × 4 = 28, et la paire extérieure contient 3 × 7 = 21.

+15 tests cachés à la soumission

Pour aller plus loin

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

Solution

Il y a environ n²/2 paires de lignes, donc pour 10^4 lignes, les vérifier toutes signifie calculer 5 × 10^7 produits. La solution consiste à remarquer que la quantité d’eau dépend uniquement de la ligne la plus courte d’une paire : une fois que tu sais qu’une ligne est le côté le plus court du contenant le plus large qu’elle peut encore former, aucun contenant plus étroit qui l’utilise ne peut faire mieux. Deux pointeurs transforment ce constat en un seul parcours depuis les deux extrémités.

Vérifiez chaque paire

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Chaque récipient correspond à une paire de positions i < j. L’eau monte jusqu’à déborder par le mur le plus bas, et le fond entre les murs mesure j - i, donc la paire contient min(height[i], height[j]) × (j - i). Essayez toutes les paires, gardez la plus grande, et vous avez la réponse par définition.

Le problème, c’est le nombre de paires. n lignes en donnent n(n-1)/2 : environ 5 × 10^7 pour 10^4 lignes, et quatre fois plus à chaque fois que la liste double. Un langage compilé vient à bout de cela en une fraction de seconde, mais Python, Ruby ou R ont besoin de plusieurs secondes, et le nombre augmente trop vite pour n’importe quel langage dès que n atteint 10^5.

Algorithme

Définis best à 0.
Pour chaque i, et chaque j qui le suit, calcule min(height[i], height[j]) × (j - i).
Garde 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

Lignes les plus hautes en premier

Intuition

Considère un conteneur depuis le côté de son côté le plus court. Si la ligne i est le côté le plus court, la quantité d’eau est égale à height[i] multiplié par la distance, et l’autre ligne peut être n’importe quelle ligne au moins aussi haute. Ainsi, le meilleur conteneur pour lequel i est le côté le plus court l’associe à la ligne la plus éloignée qui est au moins aussi haute.

Pour trouver rapidement ces lignes associées, place les lignes de la plus haute à la plus basse. Lorsque vient le tour de la ligne i, toutes les lignes placées avant elle sont au moins aussi hautes, et la plus éloignée d’entre elles est soit l’index placé le plus à gauche, soit celui placé le plus à droite. Suis ces deux indices, lo et hi, et la ligne i peut contenir au maximum height[i] × max(i - lo, hi - i). La réponse est la plus grande de ces valeurs, car le meilleur conteneur est comptabilisé lorsque son côté le plus court vient à son tour.

Dans le premier exemple, les deux 7 aux positions 1 et 5 viennent en premier et contiennent 28. Le 6 à la position 7 vient ensuite, avec lo = 1 et hi = 5, et contient 6 × 6 = 36. Aucune ligne plus basse ne fait mieux. Les lignes de même hauteur peuvent venir dans n’importe quel ordre : celle des deux lignes égales qui vient en second voit la première comme une ligne associée.

Le tri coûte O(n log n) et le parcours O(n), ce qui est suffisamment rapide. Cette approche nécessite tout de même O(n) mémoire pour stocker l’ordre, et l’approche suivante élimine à la fois le tri et cette utilisation de mémoire.

Algorithme

Triez les indices par hauteur, du plus grand au plus petit.
Définissez lo et hi comme le premier indice de cet ordre, et best à 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

Commencez par le conteneur le plus large, left = 0 et right = n-1, et mesurez-le. On peut maintenant supprimer l’une des deux lignes, et le choix s’impose : supprimer la plus courte. Supposons que height[left] ≤ height[right]. Tous les autres conteneurs qui utilisent la ligne left l’associent à une ligne plus proche que right : ils sont donc plus étroits, et leur hauteur est toujours au plus égale à height[left]. Aucun ne contient plus d’eau que celle que vous avez mesurée, donc la ligne left ne peut plus servir et left avance d’un pas vers la droite. Déplacer la ligne la plus haute à la place conserverait la même limite de hauteur tout en réduisant la largeur : le résultat ne pourrait donc qu’être moins bon. Lorsque les deux hauteurs sont égales, les deux lignes ne peuvent plus servir, et déplacer l’une ou l’autre convient.

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

Avec [3, 7, 2, 5, 4, 7, 3, 6], les positions 0 et 7 contiennent 3 × 7 = 21. Le 3 est plus petit, donc left passe à 1. Les positions 1 et 7 contiennent 6 × 6 = 36, et maintenant le 6 est plus petit, donc right passe à 6. Les conteneurs suivants contiennent 15, 28, 12, 10 et 2 ; la réponse reste donc 36.

Algorithme

Définis left = 0, right = n-1 et best = 0.
Tant que left < right, calcule min(height[left], height[right]) × (right - left) et conserve la meilleure valeur.
Si height[left] < height[right], déplace left d’un pas vers la droite. Sinon, déplace right d’un pas vers la gauche.
Lorsque les pointeurs se rejoignent, retourne 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

La boucle à deux pointeurs est courte, donc les erreurs se nichent dans les détails.

Déplacer la ligne la plus haute. Dans le premier exemple, le résultat est 21 au lieu de 36 : la ligne de hauteur 6 à la position 7 est la plus haute de la première paire, elle est donc écartée avant même de rencontrer celle de hauteur 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.
Une erreur de décalage de un dans la largeur. Les lignes aux positions i et j sont séparées de j - i, et non de j - i + 1 ; ainsi, deux voisines contiennent un volume égal à leur hauteur la plus basse multipliée par 1.
Supposer que la réponse utilise la ligne la plus haute ou la paire extérieure. Dans le premier exemple, les deux lignes de hauteur 7 contiennent 28 et la paire extérieure 21, alors que la réponse est 36.
Débordement avec des limites plus élevées. Ici, l’eau reste en dessous de 10^8, mais avec des hauteurs et des longueurs proches de 10^5, le produit dépasse 2^31 et nécessite un entier de 64 bits.

Questions fréquentes4

Quelle est la complexité temporelle du problème du récipient contenant le plus d’eau ?

La solution à deux pointeurs s’exécute en O(n) et utilise O(1) espace supplémentaire. À chaque étape, un pointeur avance d’une position vers l’intérieur, donc il y a au plus n-1 étapes. 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 conserve cette ligne a un partenaire plus proche, donc il est plus étroit et n’est toujours pas plus haut que la ligne la plus courte. Aucun d’eux ne peut faire mieux que le récipient que tu as mesuré, donc tu peux écarter la ligne la plus courte sans perdre la réponse.

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

Oui. À chaque étape, un choix local est effectué et n’est jamais annulé : la ligne la plus courte est écartée. Ce choix est sûr, car chaque conteneur éliminé à cette étape n’est pas meilleur que ceux déjà mesurés. C’est pourquoi ce problème relève à la fois des algorithmes gloutons et de la technique des deux pointeurs.

En quoi le problème du récipient contenant le plus d’eau diffère-t-il de celui du piégeage de l’eau de pluie ?

Ici, seules les deux lignes choisies comptent et les lignes situées entre elles sont ignorées : la réponse est donc un seul rectangle. Dans Trapping Rain Water, chaque barre est pleine et l’eau s’accumule au-dessus de chaque barre jusqu’à la hauteur de la plus basse des barres les plus hautes situées de chaque côté ; la réponse est donc une somme sur toutes les positions. Les deux problèmes ont des solutions à deux pointeurs en O(n), mais les règles de déplacement des pointeurs et les éléments à additionner diffèrent.

Python

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

Cas de test

Cas 1

Cas 2

Entrée

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

Attendu

Container With Most Water

Fonction

Contraintes

Exemples

Indices

Solution

Vérifiez chaque paire

Lignes les plus hautes en premier

Deux pointeurs depuis les deux extrémités

Pièges et cas limites

Questions fréquentes4

Problèmes similaires