La technique à deux points

Maximiser la zone du conteneur avec deux pointeurs en déplacement

Dans les algorithmes qui fonctionnent avec des tableaux ou des listes, la technique à deux pointeurs se distingue par son efficacité. Dans cet article, nous l'appliquerons au problème classique du « Conteneur contenant le plus d'eau », qui recherche la plus grande surface entre deux lignes verticales sur un graphique.

Description du problème

Étant donné un tableau d'entiers non négatifs représentant les hauteurs des lignes verticales, trouvez la paire de lignes qui, avec l'axe des x, forment le conteneur avec la plus grande surface.

Exemple

Considérez le tableau height = [1, 8, 6, 2, 5, 4, 8, 3, 7]. L'objectif est de déterminer quelles deux lignes génèrent la surface maximale.

Technique des deux pointeurs

La technique utilise deux pointeurs, un au début et un à la fin du tableau, en les déplaçant itérativement vers le centre pour trouver la solution optimale.

Pas à pas

1. Démarrage :

   • maxArea est initialisé à 0, stockant la plus grande zone trouvée jusqu'à présent.
   • Deux pointeurs, l (gauche) et r (droite), sont positionnés respectivement au début et à la fin du tableau.

2. Itération :

   • La boucle continue tant que l est inférieur à r.
   • La zone entre les lignes de l et r est calculée comme min(height[l], height[r]) * (r - l).
   • maxArea est mis à jour si la zone calculée est plus grande.

3. Mouvement des pointeurs :

   • Pour optimiser la recherche, le pointeur pointant vers la plus petite ligne est déplacé :
     • Si height[l] < height[r], incrémentez l.
     • Sinon, décrémentez r.

4. Retour :

   • Lorsque l et r se croisent, la boucle se termine et maxArea contient la surface maximale.

Exemple détaillé

Analysons le tableau height = [1, 8, 6, 2, 5, 4, 8, 3, 7] :

1. Démarrage :

   • maxArea = 0
   • l = 0 (hauteur 1), r = 8 (hauteur 7)

2. Première itération :

   • Zone : min(1, 7) * (8 - 0) = 8
   • maxArea = max(0, 8) = 8
   • Bougez l (parce que height[l] < height[r])

3. Deuxième itération :

   • l = 1 (hauteur 8), r = 8 (hauteur 7)
   • Zone : min(8, 7) * (8 - 1) = 49
   • maxArea = max(8, 49) = 49
   • Déplacer r

... et ainsi de suite, en répétant le processus jusqu'à ce que les mains se rencontrent.

Le résultat final sera maxArea = 49.

Allez solution

Suivez le code Go implémentant la technique :

package maxarea

func maxArea(height []int) int {
    maxArea := 0
    l, r := 0, len(height)-1

    for l < r {
        area := min(height[l], height[r]) * (r - l)
        maxArea = max(maxArea, area)
        if height[l] < height[r] {
            l++
        } else {
            r--
        }
    }
    return maxArea
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Conclusion

La technique des deux pointeurs offre une solution efficace aux problèmes liés aux tableaux. Dans le cas du « Conteneur avec le plus d'eau », cela garantit une complexité temporelle linéaire, ce qui en fait une approche idéale.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!