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] = [a_i, b_i]. À la i^ième requête, Alice est en train de construire a_i tandis que Bob est en train de construire b_i.

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 :

• Entrée : hauteurs = [6,4,8,5,2,7], requêtes = [[0,1],[0,3],[2,4],[3,4] ,[2,2]]
• Sortie : [2,5,-1,5,2]
• Explication : Dans la première requête, Alice et Bob peuvent déménager dans le bâtiment 2 puisque les hauteurs[0] < hauteurs[2] et hauteurs[1] &Lt ; hauteurs[2].
  • Dans la deuxième requête, Alice et Bob peuvent déménager dans le bâtiment 5 puisque les hauteurs[0] < hauteurs[5] et hauteurs[3] &Lt ; hauteurs[5].
  • Dans la troisième requête, Alice ne peut pas rencontrer Bob puisqu'Alice ne peut déménager dans aucun autre bâtiment.
  • Dans la quatrième requête, Alice et Bob peuvent déménager dans le bâtiment 5 puisque les hauteurs[3] < hauteurs[5] et hauteurs[4] &Lt ; hauteurs[5].
  • Dans la cinquième requête, Alice et Bob sont déjà dans le même bâtiment.
  • Pour ans[i] != -1, on peut montrer que ans[i] est le bâtiment le plus à gauche où Alice et Bob peuvent se rencontrer.
  • Pour ans[i] == -1, on peut montrer qu'il n'y a aucun bâtiment où Alice et Bob peuvent se rencontrer.

Exemple 2 :

• Entrée : hauteurs = [5,3,8,2,6,1,4,6], requêtes = [[0,7],[3,5],[5,2],[ 3,0],[1,6]]
• Sortie : [7,6,-1,4,6]
• Explication : Dans la première requête, Alice peut directement déménager dans l'immeuble de Bob puisque les hauteurs[0] < hauteurs[7].
  • Dans la deuxième requête, Alice et Bob peuvent déménager dans le bâtiment 6 puisque les hauteurs[3] < hauteurs[6] et hauteurs[5] &Lt ; hauteurs[6].
  • Dans la troisième requête, Alice ne peut pas rencontrer Bob puisque Bob ne peut pas déménager dans un autre bâtiment.
  • Dans la quatrième requête, Alice et Bob peuvent déménager dans le bâtiment 4 puisque les hauteurs[3] < hauteurs[4] et hauteurs[0] &Lt ; hauteurs[4].
  • Dans la cinquième requête, Alice peut déménager directement dans le bâtiment de Bob puisque les hauteurs[1] < hauteurs[6].
  • Pour ans[i] != -1, on peut montrer que ans[i] est le bâtiment le plus à gauche où Alice et Bob peuvent se rencontrer.
  • Pour ans[i] == -1, on peut montrer qu'il n'y a aucun bâtiment où Alice et Bob peuvent se rencontrer.

Contraintes :

• 1 <= hauteurs.longueur <= 5 * 10⁴
• 1 <= hauteurs[i] <= 10⁹
• 1 <= requêtes.length <= 5 * 10⁴
• requêtes[i] = [a_i, b_i]
• 0 <= a_i, b_i <= hauteurs.longueur - 1

Indice :

1. Pour chaque requête [x, y], si x > y, échangez x et y. Maintenant, nous pouvons supposer que x <= y.
2. Pour chaque requête [x, y], si x == y ou heights[x] < hauteurs[y], alors la réponse est y puisque x ≤ y.
3. Sinon, il faut trouver le plus petit indice t tel que y < t et hauteurs[x] &Lt ; hauteurs[t]. Notez que heights[y] <= heights[x], donc heights[x] < les hauteurs[t] sont une condition suffisante.
4. Pour trouver l'index t pour chaque requête, triez les requêtes par ordre décroissant de y. Parcourez les requêtes tout en conservant une pile monotone sur laquelle nous pouvons effectuer une recherche binaire pour trouver l'index t.

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.

Points clés

1. Alice et Bob peuvent déménager dans un autre bâtiment si sa hauteur est strictement supérieure au bâtiment actuel.
2. Pour chaque requête, recherchez le point de rendez-vous valide le plus à gauche, ou renvoyez -1 si aucun bâtiment de ce type n'existe.
3. Les contraintes exigent une solution meilleure qu'une approche naïve O(n²).

Approche

1. Observations :

   • Si a == b, Alice et Bob sont déjà dans le même bâtiment.
   • Si les hauteurs[a] < hauteurs[b], l'immeuble de Bob est le point de rendez-vous.
   • Sinon, trouvez le plus petit indice de bâtiment t > b où :
     • hauteurs[a] < hauteurs[t]
     • heights[b] <= heights[t] (car b est déjà inférieur à a dans la comparaison des hauteurs).

2. Optimisation à l'aide d'une pile monotonique :

   • Une pile monotone permet de suivre efficacement les bâtiments valides vers lesquels Alice et Bob peuvent déménager. Les bâtiments sont ajoutés à la pile de manière à garantir que les hauteurs soient par ordre décroissant, permettant ainsi des recherches binaires rapides.

3. Tri des requêtes :

   • Triez les requêtes par ordre décroissant de b pour traiter en premier les bâtiments avec des indices plus grands. Cela garantit que nous construisons la pile efficacement à mesure que nous passons d'indices supérieurs à inférieurs.

4. Recherche binaire sur pile :

   • Pour chaque requête, utilisez la recherche binaire sur la pile monotone pour trouver le plus petit index t qui satisfait aux conditions.

Planifier

1. Trier les requêtes en fonction du plus grand des deux indices (b) par ordre décroissant.
2. Parcourez le tableau vers l'arrière tout en conservant une pile monotone d'indices valides.
3. Pour chaque requête, vérifiez les cas triviaux (a == b ou heights[a] < heights[b]).
4. Pour les cas non triviaux, utilisez la pile pour trouver le bâtiment valide le plus à gauche via une recherche binaire.
5. Renvoyer les résultats dans l'ordre de requête d'origine.

Étapes de la solution

1. Requêtes de prétraitement :

   • Assurez-vous que a <= b dans chaque requête par souci de cohérence.
   • Trier les requêtes par b par ordre décroissant.

2. Parcourir les requêtes :

   • Maintenir une pile monotone pendant que nous parcourons le tableau.
   • Pour chaque requête :
     • Si a == b, la réponse est b.
     • Si les hauteurs[a] < hauteurs[b], la réponse est b.
     • Sinon, utilisez la pile pour trouver le plus petit index valide t > b.

   • Recherche binaire sur pile :

     • Utilisez la recherche binaire pour trouver rapidement le plus petit index t sur la pile qui satisfait les hauteurs[t] > hauteurs[a].

   • Rétablir la commande d'origine :

     • Mappez les résultats avec les index de requête 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));
   ?>
   

   Explication:

   1. Tri des requêtes : Les requêtes sont triées par b par ordre décroissant pour traiter en premier les index plus grands, ce qui nous permet de mettre à jour notre pile monotone au fur et à mesure du traitement.
   2. Pile monotone : La pile est utilisée pour suivre les indices de construction où Alice et Bob peuvent se rencontrer. Nous ne conservons que les bâtiments qui ont une hauteur supérieure à tous les bâtiments vus précédemment dans la pile.
   3. Recherche binaire : Lorsque nous répondons à chaque requête, nous utilisons la recherche binaire pour trouver efficacement le plus petit index t où les conditions sont remplies.

   Exemple de procédure pas à pas

   Saisir:

   • hauteurs = [6,4,8,5,2,7]
   • requêtes = [[0,1],[0,3],[2,4],[3,4],[2,2]]

   Processus:

   1. Trier les requêtes :

      • Requêtes indexées : [(2,4), (3,4), (0,3), (0,1), (2,2)]

   2. Construire une pile monotone :

      • Commencez par l'index le plus élevé et ajoutez des indices à la pile :
        • À l'index 5 : Pile = [5]
        • À l'index 4 : Pile = [5, 4]
        • ...

   3. Traitement des requêtes :

      • Pour la requête [0,1], hauteurs[0] < hauteurs[1] : Résultat = 2.
      • ...

   Sortir:

   [2, 5, -1, 5, 2]

   Complexité temporelle

   1. Tri des requêtes : O (Q log Q) où Q est le nombre de requêtes.
   2. Construction de pile monotone : O(N) où N est la longueur des hauteurs.
   3. Recherche binaire pour chaque requête : O (Q log N).

   Global : O(N Q log (Q N)).

   Sortie pour exemple

   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 :

   • 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!