. Distance maximale dans les tableaux

624. Distance maximale dans les tableaux

Difficulté :Moyen

Sujets :Array, Greedy

Vous recevez m tableaux, où chaque tableau est trié parordre croissant.

Vous pouvez récupérer deux entiers dans deux tableaux différents (chaque tableau en choisit un) et calculer la distance. Nous définissons la distance entre deux entiers a et b comme étant leur différence absolue |a - b|.

Retourla distance maximale.

Exemple 1 :

• Entrée :tableaux = [[1,2,3],[4,5],[1,2,3]]
• Sortie :4
• Explication :Une façon d'atteindre la distance maximale 4 est de choisir 1 dans le premier ou le troisième tableau et d'en choisir 5 dans le deuxième tableau.

Exemple 2 :

• Entrée :tableaux = [[1],[1]]
• Sortie :0

Contraintes :

• m == tableaux.longueur
• 2 <= m <= 10⁵
• 1 <= tableaux[i].length <= 500
• -10⁴<= tableaux[i][j] <= 10⁴
• arrays[i] est trié parordre croissant.
• Il y aura au plus 10⁵entiers dans tous les tableaux.

Solution :

Nous devons calculer la distance maximale possible entre deux entiers, chacun choisi dans des tableaux différents. L'observation clé est que la distance maximale se situera très probablement entre la valeur minimale d'un tableau et la valeur maximale d'un autre tableau.

Pour résoudre ce problème, nous pouvons suivre ces étapes :

1. Suivez la valeur minimale et la valeur maximale lorsque vous parcourez les tableaux.
2. Pour chaque tableau, calculez la distance maximale potentielle en comparant le minimum du tableau actuel avec le maximum global et le maximum du tableau actuel avec le minimum global.
3. Mettez à jour le minimum et le maximum globaux au fur et à mesure.

Implémentons cette solution en PHP :624. Distance maximale dans les tableaux

        
Explication:
        

         
min_valueetmax_valuesont initialisés avec les valeurs minimale et maximale du premier tableau.
         
Lorsque nous parcourons chaque tableau en commençant par le second :
          

           
Nous calculons la distance en comparant le minimum global avec le maximum du tableau actuel et le maximum global avec le minimum du tableau actuel.
           
Mettez à jour la max_distance chaque fois qu'une distance plus grande est trouvée.
           
Mettez à jour min_value et max_value pour refléter les valeurs minimales et maximales rencontrées jusqu'à présent.
          
         
Enfin, la fonction renvoie la distance maximale trouvée.
        
Cette solution s'exécute en temps O(m), où m est le nombre de tableaux, ce qui la rend efficace compte tenu des contraintes du problème.
Liens de contact
Si vous avez trouvé cette série utile, pensez à donner une étoile audépôtsur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !
Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :
        

         
LinkedIn
         
GitHub
        
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!