2940. Trouvez le 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,Empiler,Arbre indexé binaire,Arbre de segments,Tas (file d'attente prioritaire),Pile monotone

Vous recevez un tableau indexé 0hauteursd'entiers positifs, oùhauteurs[i]représente la hauteur duavecbâtiment.

Si une personne est dans un immeubleje, ils peuvent déménager dans n'importe quel autre bâtimentjsi et seulement sije < jethauteurs[i] < hauteurs[j].

Vous recevez également un autre tableaurequêtesoùrequêtes[i] = [ai, bi]. Sur leavecrequête, Alice est dans le bâtimentaipendant que Bob est en train de construirebi.

Renvoie un tableauansoùet[je]est l'index du bâtiment le plus à gauche où Alice et Bob peuvent se rencontrer sur laavecrequête. Si Alice et Bob ne peuvent pas déménager dans un bâtiment commun lors d'une requêteje, ensembleet[je]à-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 heights[0] < heights[2] et heights[1] < heights[2].
  • Dans la deuxième requête, Alice et Bob peuvent déménager dans le bâtiment 5 puisque heights[0] < heights[5] et heights[3] < heights[5].
  • Dans la troisième requête, Alice ne peut pas rencontrer Bob puisqu'Alice 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 5 puisque heights[3] < heights[5] et heights[4] < heights[5].
  • Dans la cinquième requête, Alice et Bob se trouvent déjà dans le même bâtiment.
  • Pour ans[i] != -1, on peut montrer que and[i] est le bâtiment le plus à gauche où Alice et Bob peuvent se rencontrer.
  • Pour and[i] == -1, on peut montrer qu'il n'y a aucun bâtiment où Alice et Bob peuvent ...
    [Courte citation de 8% de l'article original]