Next Greater Element I
On vous donne deux tableaux d’entiers distincts, nums1 et nums2, et chaque valeur de nums1 apparaît également dans nums2. L’élément suivant supérieur d’une valeur x est la première valeur située à droite de x dans nums2 qui est supérieure à x, ou -1 si aucune valeur de ce type n’existe.
Renvoyez un tableau contenant l’élément suivant supérieur de chaque valeur de nums1, dans l’ordre de nums1.
Fonction
- nums1integer-array
- les valeurs auxquelles répondre, qui se trouvent toutes dans nums2
- nums2integer-array
- le tableau dans lequel vous regardez à droite de chaque valeur
- Renvoieinteger-array
- l’élément suivant supérieur à chaque valeur de nums1, ou -1, dans l’ordre de nums1
Contraintes
1 ≤ nums1.length ≤ nums2.length ≤ 1040 ≤ nums1[i], nums2[i] ≤ 104- Toutes les valeurs de
nums1sont distinctes, et toutes les valeurs denums2sont distinctes. - Chaque valeur de
nums1apparaît dansnums2.
Exemples
- Entrée
- nums1 = [3, 8, 1]nums2 = [1, 6, 3, 8, 2]
- Sortie
- [8, -1, 6]
- Explication
- Après le 3 dans
nums2viennent 8 et 2, et 8 est le premier nombre supérieur à 3. Seul 2 suit le 8, donc 8 reçoit -1. La valeur juste après 1 est 6, qui est déjà supérieure.
- Entrée
- nums1 = [5, 2]nums2 = [2, 9, 5, 4]
- Sortie
- [-1, 9]
- Explication
- Seul 4 suit 5, et 4 est plus petit, donc 5 reçoit -1. La valeur juste après 2 est 9. Les réponses suivent l’ordre de
nums1, et non celui denums2.
- Entrée
- nums1 = [10, 0]nums2 = [0, 10, 11]
- Sortie
- [11, 10]
- Explication
- La première valeur après 10 est 11. La première valeur après 0 est 10, qui est plus grande, donc 0 reçoit 10 même si 11 vient plus tard et est encore plus grande.
+14 tests cachés à la soumission
Pour aller plus loin
Pour chaque position de nums2, peux-tu renvoyer le nombre d’étapes vers la droite qui séparent cette position de son prochain élément supérieur, en un seul parcours ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Parcourir vers la droite à partir de chaque valeur de
nums1peut coûter jusqu’à 10^4 étapes par valeur. Les réponses dépendent uniquement denums2. Pourrais-tu déterminer l’élément suivant supérieur à chaque valeur denums2en un seul parcours, puis rechercher les valeurs denums1?Parcourez
nums2de gauche à droite et conservez les valeurs qui n’ont pas encore rencontré de valeur plus grande. Lorsqu’une nouvelle valeur arrive, elle constitue la réponse pour chaque valeur en attente qui est plus petite qu’elle. Les valeurs en attente forment toujours une séquence décroissante, donc les plus petites se trouvent au sommet d’une pile.Pour chaque valeur de
nums2: tant que le sommet de la pile est inférieur à cette valeur, dépilez le sommet et enregistrez la valeur actuelle comme réponse dans une table de hachage. Puis empilez la valeur actuelle. À la fin, récupérez dans la table la réponse pour chaque valeur denums1, et renvoyez -1 pour une valeur qui n’a jamais été dépilée.
Solution
Pour une valeur, la réponse consiste à parcourir les éléments à sa droite, mais le faire pour chaque valeur de nums1 peut coûter jusqu’à nums1.length × nums2.length étapes. Les réponses dépendent uniquement de nums2, donc tu peux trouver d’un seul coup l’élément suivant plus grand pour chaque valeur de nums2 à l’aide d’une pile monotone, les stocker dans une table de hachage et répondre pour nums1 par consultation.
Trouvez chaque valeur et parcourez vers la droite
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Suivez la définition. Pour une valeur x de nums1, parcourez nums2 jusqu’à atteindre x. Continuez ensuite à parcourir le tableau et arrêtez-vous à la première valeur supérieure à x. Si vous atteignez la fin sans en trouver, la réponse est -1.
C’est correct, car le parcours visite dans l’ordre les valeurs situées à droite de x ; la première valeur supérieure rencontrée est donc la première valeur supérieure qui existe à cet endroit.
Cette méthode est lente lorsque les réponses sont éloignées ou absentes. Si nums2 est décroissant, aucun parcours ne trouve de valeur supérieure, et chaque valeur de nums1 est parcourue jusqu’à la fin. Avec m valeurs dans nums1 et n dans nums2, cela représente jusqu’à m × n étapes : 10^8 lorsque les deux tableaux contiennent 10^4 valeurs. Chaque parcours repasse également sur des éléments déjà parcourus lors des précédents.
Algorithme
- Parcourez chaque valeur
xdenums1. - Trouvez l’indice
joùnums2[j]est égal àx. - Parcourez
nums2à partir dej+1et arrêtez-vous à la première valeur supérieure àx. - Ajoutez cette valeur, ou -1 si le parcours a atteint la fin.
- Renvoyez les réponses recueillies.
def nextGreaterElement(nums1, nums2):
result = []
for x in nums1:
j = 0
while nums2[j] != x:
j += 1
answer = -1
for k in range(j + 1, len(nums2)):
if nums2[k] > x:
answer = nums2[k]
break
result.append(answer)
return resultPile monotone et table de hachage
Intuition
Inversez la question. Au lieu de demander, pour chaque valeur, ce qui vient après elle, parcourez nums2 une fois et laissez chaque nouvelle valeur répondre aux valeurs précédentes qu’elle dépasse. Gardez sur une pile les valeurs qui n’ont pas encore de réponse. Lorsqu’une valeur arrive, dépilez toutes les valeurs plus petites qui se trouvent au sommet : la nouvelle valeur est la première valeur plus grande à leur droite, c’est donc leur réponse. Empilez ensuite la nouvelle valeur, qui attend encore sa propre réponse.
Parcourez nums2 = [1, 6, 3, 8, 2]. Empilez 1. Puis 6 arrive et dépasse 1, donc 1 correspond à 6 ; empilez 6. Puis 3 arrive, ne dépasse pas 6 et est empilée au-dessus : la pile est [6, 3]. Puis 8 dépile 3 et 6, donc les deux correspondent à 8 ; empilez 8. Puis 2 est empilé. La pile se termine par [8, 2], et ces deux valeurs n’ont pas de réponse. Pour nums1 = [3, 8, 1], la table donne [8, -1, 6].
La pile est toujours décroissante du bas vers le haut, car une valeur n’est empilée qu’après que toutes les valeurs plus petites situées au-dessus d’elle ont été dépilées. C’est pourquoi vous n’avez besoin de regarder que le sommet. Une valeur quitte la pile dès que la première valeur plus grande apparaît ; la réponse que vous enregistrez est donc la première, et non la plus grande.
Chaque valeur de nums2 est empilée une fois et dépilée au plus une fois ; la boucle interne effectue donc au plus n dépilements au total sur tout le parcours. Avec les m recherches, le temps d’exécution est de O(n + m). La table fait le lien entre les deux tableaux : les valeurs sont distinctes, donc une valeur constitue une clé sûre, même si elle se trouve à des positions différentes dans nums1 et nums2. Les solutions C et R utilisent comme table un tableau de 10^4+1 cases, indexé par valeur, ce qui fonctionne car aucune valeur ne dépasse 10^4.
Algorithme
- Créez une table de hachage vide et une pile vide.
- Pour chaque valeur de
nums2, dépilez toutes les valeurs plus petites situées au sommet de la pile et associez-les à la valeur actuelle. - Empilez la valeur actuelle.
- Pour chaque valeur de
nums1, renvoyez la réponse qui lui est associée, ou -1 si elle n'en a pas.
def nextGreaterElement(nums1, nums2):
next_greater = {}
stack = [] # values still waiting for a greater one, decreasing from bottom to top
for value in nums2:
# value is the first greater value to the right of every smaller value on the stack.
while stack and stack[-1] < value:
next_greater[stack.pop()] = value
stack.append(value)
# Whatever is still on the stack has no greater value to its right.
return [next_greater.get(x, -1) for x in nums1]
Pièges et cas limites
La pile elle-même se résume à quelques lignes de code ; les erreurs concernent ce que vous enregistrez et l’endroit où vous cherchez.
- Enregistrer la plus grande valeur à droite au lieu de la première valeur plus grande. Dans
nums2 = [3, 5, 1, 2, 4, 9, 0], la réponse pour 1 est 2, et non 9. - Renvoyer les réponses dans l’ordre de
nums2, ou pour chaque valeur denums2. Le résultat contient une entrée par valeur denums1, dans son ordre. - Renvoyer un indice au lieu d’une valeur. Le problème demande la valeur plus grande elle-même.
- Lire
nums2à l’indice correspondant à une valeur dansnums1. Une même valeur se trouve à des positions différentes dans les deux tableaux ; recherchez-la par sa valeur, c’est à cela que sert la table de correspondance. - Oublier les valeurs restantes dans la pile à la fin. Elles n’ont jamais rencontré de valeur plus grande, donc leur réponse est -1 ; une recherche dans la table sans valeur par défaut échoue ou ne renvoie rien pour elles.
- Chercher à gauche ou revenir au début de
nums2. Seules les valeurs à droite comptent, et le tableau ne revient pas au début.
Questions fréquentes4
Quelle est la complexité temporelle de Next Greater Element I ?
La solution avec une pile monotone s’exécute en O(n + m), où n est la longueur de nums2 et m celle de nums1. Chaque valeur de nums2 est empilée et dépilée au plus une fois, et chaque valeur de nums1 correspond à une recherche dans la map. La map et la pile utilisent O(n) d’espace. Le balayage vers la droite à partir de chaque valeur prend un temps de O(n·m).
Qu’est-ce qu’une pile monotone ?
C’est une pile dont les valeurs restent triées de bas en haut, ici par ordre décroissant. Avant d’empiler une nouvelle valeur, tu dépiles tout ce qui briserait l’ordre, et c’est là que le travail se fait : chaque valeur dépilée a trouvé sa première valeur plus grande à droite. Cette méthode résout les problèmes du prochain élément plus grand, du prochain élément plus petit et les questions similaires en temps linéaire.
Pourquoi Next Greater Element I a-t-il besoin d’une table de hachage ?
Le parcours de la pile produit les réponses dans l’ordre où les valeurs en sortent, en les associant aux valeurs de nums2. La sortie doit suivre l’ordre de nums1, où les mêmes valeurs se trouvent à d’autres positions. Comme toutes les valeurs sont distinctes, une mappe des valeurs vers les réponses relie les deux tableaux avec un accès en temps constant pour chaque valeur.
Qu’est-ce qui change si nums2 est circulaire ?
La recherche d'une valeur plus grande peut alors continuer à partir du début du tableau. Parcourez la pile de la même manière deux fois sur le tableau, en utilisant l'indice i % n pour i de 0 à 2n-1, et n'empilez les valeurs que pendant le premier tour. Les valeurs qui sont encore dans la pile après les deux tours n'ont aucune valeur plus grande nulle part ; leur réponse est donc -1.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
Python
def nextGreaterElement(nums1, nums2):
# Écrivez le code iciCas 1
Cas 2
Cas 3
Entrée
nums1 = [3, 8, 1] nums2 = [1, 6, 3, 8, 2]
Attendu
[8, -1, 6]