Maison >développement back-end >tutoriel php >Trouvez un bâtiment où Alice et Bob peuvent se rencontrer
2940. Trouvez le bâtiment où Alice et Bob peuvent se rencontrer
Difficulté : Difficile
Sujets : Tableau, recherche binaire, pile, arbre indexé binaire, arbre de segments, tas (file d'attente prioritaire), pile monotonique
Vous recevez un tableau indexé à 0 de hauteurs d'entiers positifs, où hauteurs[i] représente la hauteur du ième bâtiment.
Si une personne se trouve dans le bâtiment i, elle peut déménager dans n'importe quel autre bâtiment j si et seulement si i < j et hauteurs[i] &Lt ; hauteurs[j].
Vous recevez également un autre tableau de requêtes où requêtes[i] = [ai, bi]. À la iième requête, Alice est en train de construire ai tandis que Bob est en train de construire bi.
Renvoyer un tableau ans où ans[i] est l'index du bâtiment le plus à gauche où Alice et Bob peuvent se rencontrer sur la ième requête. Si Alice et Bob ne peuvent pas déménager vers un bâtiment commun lors de la requête i, définissez ans[i] sur -1.
Exemple 1 :
Exemple 2 :
Contraintes :
Indice :
Solution :
Le problème nécessite de déterminer le bâtiment le plus à gauche où Alice et Bob peuvent se rencontrer compte tenu de leurs bâtiments de départ et de leurs règles de déplacement. Chaque requête consiste à trouver un point de rendez-vous en fonction de la hauteur des bâtiments. Ceci est un défi en raison des contraintes de mouvement et de la nécessité d'un calcul efficace.
Observations :
Optimisation à l'aide d'une pile monotonique :
Tri des requêtes :
Recherche binaire sur pile :
Requêtes de prétraitement :
Parcourir les requêtes :
Recherche binaire sur pile :
Rétablir la commande d'origine :
Résultats de retour.
Implémentons cette solution en PHP : 2940. Trouvez le bâtiment où Alice et Bob peuvent se rencontrer
<?php /** * @param Integer[] $heights * @param Integer[][] $queries * @return Integer[] */ function leftmostBuildingQueries($heights, $queries) { ... ... ... /** * go to ./solution.php */ } /** * @param $queries * @return array */ private function getIndexedQueries($queries) { ... ... ... /** * go to ./solution.php */ } /** * @param $stack * @param $a * @param $heights * @return mixed|null */ private function findUpperBound($stack, $a, $heights) { ... ... ... /** * go to ./solution.php */ } class IndexedQuery { public $queryIndex; public $a; // Alice's index public $b; // Bob's index /** * @param $queryIndex * @param $a * @param $b */ public function __construct($queryIndex, $a, $b) { $this->queryIndex = $queryIndex; $this->a = $a; $this->b = $b; } } // Test the function $heights = [6, 4, 8, 5, 2, 7]; $queries = [[0, 1], [0, 3], [2, 4], [3, 4], [2, 2]]; print_r(leftmostBuildingQueries($heights, $queries)); $heights = [5, 3, 8, 2, 6, 1, 4, 6]; $queries = [[0, 7], [3, 5], [5, 2], [3, 0], [1, 6]]; print_r(leftmostBuildingQueries($heights, $queries)); ?>
Trier les requêtes :
Construire une pile monotone :
Traitement des requêtes :
[2, 5, -1, 5, 2]
Global : O(N Q log (Q N)).
Entrée :
$heights = [6, 4, 8, 5, 2, 7]; $queries = [[0, 1], [0, 3], [2, 4], [3, 4], [2, 2]];
Sortie :
print_r(findBuilding($heights, $queries)); // [2, 5, -1, 5, 2]
Cette approche gère efficacement des contraintes importantes en tirant parti d'une pile monotone et d'une recherche binaire. Il garantit un traitement optimal des requêtes tout en conservant l'exactitude.
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 :
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!