Stock Span Problem
Vous obtenez le cours de clôture d’une action pour chaque jour : prices[i] est le cours du jour i. La durée du jour i est le nombre de jours consécutifs, se terminant au jour i inclus, pendant lesquels le cours était inférieur ou égal à prices[i].
Retournez la durée de chaque jour, dans le même ordre que prices. Chaque durée est d’au moins 1, car un jour compte toujours pour lui-même.
Fonction
- pricesinteger-array
- le prix de chaque jour, dans l’ordre
- Renvoieinteger-array
- la durée de chaque jour, dans le même ordre
Contraintes
1 ≤ prices.length ≤ 1041 ≤ prices[i] ≤ 105- Une journée antérieure avec le même prix compte dans la période ; seul un prix strictement supérieur l’interrompt.
Exemples
- Entrée
- prices = [31, 27, 14, 21, 30, 18, 40]
- Sortie
- [1, 1, 1, 2, 4, 1, 7]
- Explication
- Le jour 3, à 21, remonte au-delà de 14 et s’arrête à 27 : portée de 2. Le jour 4, à 30, s’arrête à 31 : portée de 4. Le jour 6, à 40, dépasse tous les prix précédents et couvre les 7 jours.
- Entrée
- prices = [8, 8, 3, 8]
- Sortie
- [1, 2, 1, 4]
- Explication
- Les prix égaux sont pris en compte, donc le jour 1 à 8 couvre le jour 0 et obtient 2. Le jour 3 à 8 couvre le jour 3 et les deux 8 précédents, soit une période de 4.
- Entrée
- prices = [50, 40, 30, 20]
- Sortie
- [1, 1, 1, 1]
- Explication
- Chaque jour est moins cher que le jour précédent, donc aucun intervalle ne remonte au-delà du jour lui-même et chaque intervalle vaut 1.
Pour aller plus loin
Les prix arrivent maintenant un par un, et tu dois indiquer chaque intervalle au fur et à mesure qu’un prix arrive. Quelle approche fonctionne toujours, et que conserve-t-elle entre les appels ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Compter à rebours depuis chaque jour répète le travail : pour 8000 jours au même prix, le dernier jour à lui seul remonte 8000 jours. En remontant à partir d’aujourd’hui, quels jours antérieurs peux-tu sauter définitivement ?
Dès que le prix du jour est au moins aussi élevé que celui d’un jour précédent, ce jour précédent ne peut jamais être celui qui arrête une période ultérieure : le jour présent est plus proche et son prix est au moins aussi élevé. Seuls comptent encore les jours dont le prix est plus élevé que celui de tous les jours qui les suivent, et leurs prix diminuent de l’ancien au plus récent.
Parcourez les jours dans l’ordre et gardez sur une pile, sous forme d’indices, les jours précédents qui comptent encore. Avant de répondre pour aujourd’hui, dépilez chaque jour dont le prix est inférieur ou égal à celui d’aujourd’hui. Une pile vide signifie que l’étendue remonte jusqu’au jour 0 ; sinon, elle s’arrête un jour après le jour qui se trouve au sommet. Puis empilez aujourd’hui.
Solution
L’étendue d’une journée se termine à la première journée précédente dont le prix est strictement supérieur. Revenir en arrière pour la trouver peut coûter jusqu’à n étapes par jour. À la place, conserve uniquement les journées qui peuvent encore arrêter une étendue future : une pile d’indices dont les prix sont strictement décroissants permet de trouver chaque limite en un seul parcours.
Compter à rebours à partir de chaque jour
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Suivez la définition. Pour le jour i, reculez d’un jour à la fois tant que le prix de ce jour est inférieur ou égal à prices[i], en comptant aussi le jour i. Le premier prix strictement supérieur, ou le début du tableau, met fin au parcours.
Aucun parcours ne réutilise un parcours précédent. Avec des prix constants ou croissants, chaque parcours remonte jusqu’au jour 0 : n = 10^4 jours représentent environ 5 × 10^7 étapes.
Algorithme
- Créez
span, un tableau aussi long queprices. - Pour chaque jour
i, définissez un compteur à 0 et un pointeurjài. - Tant que
j ≥ 0etprices[j] ≤ prices[i], ajoutez 1 au compteur et reculez le pointeurjd’un jour. - Stockez le compteur dans
span[i]. Après le dernier jour, renvoyezspan.
def stockSpan(prices):
span = []
for i in range(len(prices)):
count = 0
j = i
# Count today and every earlier day in a row that is not more expensive.
while j >= 0 and prices[j] <= prices[i]:
count += 1
j -= 1
span.append(count)
return spanPile monotone des jours plus chauds
Intuition
Appelez bloqueur le jour antérieur le plus proche dont le prix est strictement supérieur. L'intervalle est today - blocker, ou today + 1 lorsqu'il n'y en a aucun.
Dans le premier exemple, le jour 3 coûte 21 et le jour 4 coûte 30. Chaque parcours ultérieur atteint d'abord le jour 4, et tout prix qui dépasse 30 dépasse aussi 21 ; le jour 3 ne peut donc plus jamais bloquer. En général, lorsque le jour courant arrive, tout candidat antérieur dont le prix est inférieur ou égal à celui du jour courant est écarté : retirez-le de la pile. Le jour qui reste au sommet est le bloqueur du jour courant. Ensuite, empilez le jour courant.
Les prix sur la pile décroissent strictement du bas vers le haut ; le premier qui reste est donc le prix supérieur le plus proche. Dans le premier exemple, le jour 4 retire les jours 3 et 1 de la pile, puis s'arrête au jour 0, pour un intervalle de 4 - 0 = 4. Chaque jour est empilé une fois et retiré au plus une fois ; le parcours s'exécute donc en O(n).
Algorithme
- Créez le tableau
spanet une pile vide pour les indices des jours. - Pour chaque jour
today, dépilez les indices de la pile tant que leur prix est inférieur ou égal àprices[today]. - Si la pile est vide, l’étendue est
today + 1; sinon, elle est égale àtodaymoins l’indice au sommet. - Empilez
todayet passez au jour suivant. Retournezspan.
def stockSpan(prices):
span = [0] * len(prices)
higher = [] # indices of earlier days, prices strictly falling toward the top
for today, price in enumerate(prices):
# A day that is not more expensive than today can never stop a later span.
while higher and prices[higher[-1]] <= price:
higher.pop()
# The span reaches back to the nearest more expensive day, or to day 0.
span[today] = today - higher[-1] if higher else today + 1
higher.append(today)
return span
Pièges et cas limites
- Retirer en cas de
<au lieu de<=. Dans[8, 8, 3, 8], le dernier jour a une portée de 4 ; s’arrêter au 8 précédent donne 2. - Écrire
todayau lieu detoday + 1lorsque la pile est vide. Le jour 0 doit recevoir 1, et non 0. - Ne retirer qu’un seul élément par jour. Dans le premier exemple, 40 doit éliminer les jours 5, 4 et 0. S’arrêter après le jour 5 fait du jour 4 son bloqueur apparent, pour une portée de 2 au lieu de 7.
- En Lua et en R, les tableaux commencent à 1. Avec des indices à partir de 1, la portée lorsque la pile est vide est
today, et nontoday + 1.
Questions fréquentes4
Quelle est la complexité temporelle du problème des intervalles boursiers ?
O(n) en temps et O(n) d’espace supplémentaire avec la pile monotone, puisqu’un jour quitte la pile au plus une fois. Parcourir à rebours depuis chaque jour prend O(n²) lorsque les prix augmentent constamment ou restent stables.
La pile doit-elle stocker les prix ou les indices des jours ?
Les indices de jour. L’intervalle correspond à un nombre de jours, et seul l’indice du bloqueur te donne cette information. prices[index] récupère le prix pour la comparaison.
Le problème du span boursier peut-il être résolu sans pile séparée ?
Oui. Commence à j = today - 1 ; tant que j ≥ 0 et que prices[j] ≤ prices[today], saute à j - span[j], puisque chaque jour à l’intérieur de cet intervalle a un prix inférieur ou égal à prices[j]. L’intervalle est today - j. Les sauts n’atterrissent que sur les jours que la pile conserverait, donc le parcours reste en O(n).
Le problème du span boursier est-il un problème de précédent élément supérieur ?
Oui, mesuré en jours : pour chaque jour, trouve le jour précédent le plus proche où le prix est strictement plus élevé et indique le nombre de jours qui les sépare. Inverse le sens du parcours ou la comparaison, et la même pile donne le suivant plus grand, le suivant plus petit ou le précédent plus petit.
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.
def stockSpan(prices):
# Écrivez le code iciTest #1
Test #2
Test #3
Argument
prices = [31, 27, 14, 21, 30, 18, 40]
Résultat attendu
[1, 1, 1, 2, 4, 1, 7]