Find Peak Element

Q: Quelle est la complexité temporelle de Find Peak Element ?

La recherche binaire s’exécute en temps O(log n) et utilise un espace O(1) , avec au plus 13 étapes pour 5000 valeurs. Le parcours depuis la gauche est en O(n) , puisqu’il peut lire chaque paire avant de trouver la baisse.

Q: La recherche binaire fonctionne-t-elle toujours lorsqu’il y a plusieurs pics ?

Oui, à condition que les voisins soient différents et que les positions au-delà des deux extrémités soient considérées comme inférieures à toutes les valeurs. Elle renvoie un pic, pas toujours le plus haut. Après une hausse, les valeurs doivent commencer à baisser au plus tard à la fin de la plage, et le premier changement de direction forme un pic ; le côté que la recherche conserve en contient donc toujours un.

Q: Le pic est-il toujours la valeur la plus élevée ?

Dans ce problème, oui : le tableau monte jusqu’à un seul sommet puis redescend, donc aucun autre élément ne peut être plus grand. Dans la version avec plusieurs sommets, ce n’est pas le cas, car toute valeur supérieure à ses deux voisines compte. C’est pourquoi la recherche compare les éléments voisins au lieu de chercher le maximum.

MoyenRecherche binaire

+10

Le tableau nums monte puis descend : chaque valeur est plus grande que la précédente jusqu’à un certain indice, et chaque valeur après cet indice est plus petite que la précédente. L’une des deux parties peut être vide, le tableau peut donc uniquement monter ou uniquement descendre. La valeur à l’indice de retournement est le pic, la seule valeur plus grande que chacun de ses voisins.

Retourne l’indice du pic en O(log n).

Fonction

findPeakElement(nums: integer-array) → integer

numsinteger-array: les valeurs augmentent jusqu’à un pic, puis diminuent
Renvoieinteger: l’indice du pic

Contraintes

1 ≤ nums.length ≤ 5000
-10⁶ ≤ nums[i] ≤ 10⁶
nums[i] != nums[i+1] pour chaque i valide.
nums augmente strictement jusqu’à un indice et diminue strictement après celui-ci, donc il y a exactement un sommet.

Exemples

Entrée: nums = [2, 5, 9, 4, 1]
Sortie: 2
Explication: Les valeurs augmentent en passant par 2, 5 et 9, puis diminuent en passant par 4 et 1. Le changement de direction se produit à 9, à l’indice 2.

Pour aller plus loin

Dans une grille où aucune cellule voisine n’est égale à une autre, un pic est une cellule plus grande que ses quatre voisines au maximum. Peux-tu en trouver un sans lire toutes les cellules ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Avec un seul pic, celui-ci est la valeur la plus grande ; un seul parcours suffit donc à le trouver en O(n). Pour obtenir O(log n), compare nums[mid] à nums[mid+1] : la pente à mid indique de quel côté du pic il se trouve, de sorte que chaque étape peut éliminer la moitié de l’intervalle.

Marchez jusqu’à ce que les valeurs commencent à diminuer

Intuition

Avant le pic, chaque valeur est inférieure à la suivante, et à partir du pic, chaque valeur est supérieure. Le pic est donc le premier indice i où nums[i] > nums[i+1], ou le dernier indice si le tableau ne fait que monter.

Lorsque le pic se trouve à la fin d’un tableau de 5000 valeurs, le parcours effectue 4999 comparaisons, tandis que la recherche binaire en nécessite 13.

Algorithme

Pour i de 0 à n-2, comparez nums[i] à nums[i+1].
Au premier i où nums[i] est supérieur, renvoyez i.
Si la boucle se termine sans baisse, renvoyez n-1.

def findPeakElement(nums):
    for i in range(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            return i  # the first step down starts at the peak
    return len(nums) - 1  # never went down: the last value is the peak

Recherche binaire sur la pente

Intuition

Examinez une paire, nums[mid] et nums[mid+1]. Une étape vers le haut signifie que le tableau est encore en train de monter, ce qui, dans ce tableau, ne se produit qu’avant le sommet : le sommet se trouve à mid+1 ou à sa droite. Une étape vers le bas signifie que vous êtes au sommet ou après celui-ci : le sommet se trouve à mid ou à sa gauche.

Conservez un intervalle [lo, hi] qui contient toujours le sommet. Une étape vers le haut déplace lo à mid+1. Une étape vers le bas déplace hi à mid, en conservant mid car il peut s’agir du sommet. Lorsque lo rejoint hi, l’unique indice restant correspond au sommet. Arrondir mid vers le bas le maintient inférieur à hi, donc mid+1 existe toujours.

Dans le premier exemple, mid = 2 donne 9 > 4, donc hi = 2 ; ensuite, mid = 1 donne 5 < 9, donc lo = 2, le sommet. 5000 valeurs nécessitent au plus 13 étapes.

Algorithme

Définissez lo = 0 et hi = n-1.
Tant que lo < hi, prenez mid = lo + (hi - lo) / 2, arrondi à l’entier inférieur.
Si nums[mid] < nums[mid+1], définissez lo = mid + 1.
Sinon, définissez hi = mid.
Retournez lo.

def findPeakElement(nums):
    lo, hi = 0, len(nums) - 1  # the peak is always inside [lo, hi]
    while lo < hi:
        mid = lo + (hi - lo) // 2  # mid < hi, so mid + 1 is a valid index
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1  # still climbing: the peak is to the right of mid
        else:
            hi = mid  # going down: the peak is mid or to its left
    return lo

Pièges et cas limites

Définir hi = mid - 1 lors d’une étape de descente. Dans [2, 5, 9, 4, 1], le premier mid est le pic lui-même, et hi = 1 l’élimine ; la recherche renvoie 1.
Comparer avec nums[mid-1] tout en arrondissant mid à l’entier inférieur. mid peut être égal à 0, auquel cas il n’y a pas de voisin à gauche.
Utiliser un intervalle semi-ouvert avec hi = n. Alors mid peut être égal à n-1, et nums[mid+1] lit au-delà de la fin, même avec une seule valeur.
Oublier le décalage en Lua et en R. La réponse reste l’indice basé sur 0 ; une position i est donc renvoyée sous la forme i-1.

Questions fréquentes3

Quelle est la complexité temporelle de Find Peak Element ?

La recherche binaire s’exécute en temps O(log n) et utilise un espace O(1), avec au plus 13 étapes pour 5000 valeurs. Le parcours depuis la gauche est en O(n), puisqu’il peut lire chaque paire avant de trouver la baisse.

La recherche binaire fonctionne-t-elle toujours lorsqu’il y a plusieurs pics ?

Oui, à condition que les voisins soient différents et que les positions au-delà des deux extrémités soient considérées comme inférieures à toutes les valeurs. Elle renvoie un pic, pas toujours le plus haut. Après une hausse, les valeurs doivent commencer à baisser au plus tard à la fin de la plage, et le premier changement de direction forme un pic ; le côté que la recherche conserve en contient donc toujours un.

Le pic est-il toujours la valeur la plus élevée ?

Dans ce problème, oui : le tableau monte jusqu’à un seul sommet puis redescend, donc aucun autre élément ne peut être plus grand. Dans la version avec plusieurs sommets, ce n’est pas le cas, car toute valeur supérieure à ses deux voisines compte. C’est pourquoi la recherche compare les éléments voisins au lieu de chercher le maximum.

def findPeakElement(nums):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Argument

nums = [2, 5, 9, 4, 1]

Résultat attendu