. Distance maximale dans les tableaux

624. Distance maximale dans les tableaux

Difficulté :Moyen

Sujets :Array, gourmand

Vous recevez m tableaux, où chaque tableau est trié par ordre 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|.

Renvoyer la 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 == arrays.length
• 2 <= m <= 10⁵
• 1 <= tableaux[i].length <= 500
• -10⁴ <= tableaux[i][j] <= 10⁴
• arrays[i] est trié par ordre croissant.
• Il y aura au plus 10⁵ entiers dans tous les tableaux.

Solution :

Nous devons calculer la distance maximale possible entre deux nombres 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_value et max_value sont initialisés avec les valeurs minimale et maximale du premier tableau.
Au fur et à mesure que 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 au référentiel sur 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!