Daily Temperatures

Q: Quelle est la complexité temporelle de Daily Temperatures ?

La solution avec une pile monotone s’exécute en O(n) temps et utilise O(n) d’espace supplémentaire. Chaque jour est empilé une fois et dépilé au plus une fois, donc la boucle interne s’exécute au plus n fois sur l’ensemble du parcours. Parcourir les jours suivants à partir de chaque jour prend un temps de O(n²) , soit environ 5 × 10^7 comparaisons pour 10^4 jours sans journée plus chaude.

Q: Pourquoi la pile stocke-t-elle des indices plutôt que des températures ?

La réponse pour un jour est une distance, today - day ; tu as donc besoin de la position du jour. L’indice t’indique également quelle entrée du tableau de réponses remplir lorsque le jour est retiré. La température est accessible en une seule consultation avec temperatures[day] , donc la stocker aussi n’apporte rien.

MoyenPile monotone

+10

Vous obtenez la température de chaque jour dans une série de jours : temperatures[i] est la température du jour i. Pour chaque jour, comptez le nombre de jours que vous devez attendre après celui-ci jusqu’à l’arrivée d’un jour strictement plus chaud. Si aucun jour plus chaud n’arrive par la suite, l’attente pour ce jour est 0.

Renvoyez un tableau de même longueur où l’entrée i correspond au temps d’attente pour le jour i.

Fonction

dailyTemperatures(temperatures: integer-array) → integer-array

temperaturesinteger-array: la température de chaque jour, dans l’ordre
Renvoieinteger-array: pour chaque jour, le nombre de jours avant un jour plus chaud, ou 0 si aucun n’arrive

Contraintes

1 ≤ temperatures.length ≤ 10⁴
30 ≤ temperatures[i] ≤ 100
Plus chaud signifie strictement plus élevé : un jour ultérieur avec la même température ne compte pas.

Exemples

Entrée: temperatures = [71, 69, 72, 70, 70, 75, 68]
Sortie: [2, 1, 3, 2, 1, 0, 0]
Explication: Le jour 0, la température est de 71, et le premier jour plus chaud est le jour 2, à 72 ; il faut donc attendre 2 jours. Les jours 3 et 4 sont tous deux à 70 : le second 70 n’est pas plus chaud, donc le jour 3 attend jusqu’au jour 5, à 75, soit 2 jours. Rien après 75 ou 68 n’est plus chaud, donc les deux obtiennent 0.

+13 tests cachés à la soumission

Pour aller plus loin

Les températures ne prennent que 71 valeurs, de 30 à 100. Comment une table indexée par température pourrait-elle répondre pour chaque jour en un seul passage de droite à gauche, et quel est le coût de ce passage ?

Solution

Pour une journée, la réponse consiste à parcourir le tableau vers l’avant, mais un parcours depuis chaque journée répète le même travail, et lorsque les journées chaudes sont rares, chaque parcours va jusqu’à la fin du tableau. La solution consiste à faire répondre chaque journée aux journées précédentes au lieu de chercher une réponse parmi les suivantes : une pile d’indices qui attendent encore, triée par température, permet d’obtenir toutes les réponses en un seul passage.

Parcourez vers l’avant à partir de chaque jour

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Fais ce que demande l’énoncé. Pour le jour i, regarde le jour i+1, puis i+2, et ainsi de suite, jusqu’au premier jour où la température est strictement plus élevée. La distance j-i est la réponse. Si tu arrives à la fin sans en trouver, la réponse reste 0.

C’est correct, car le parcours examine les jours suivants dans l’ordre : le premier jour plus chaud qu’il rencontre est donc le premier jour plus chaud qui existe. Il est également important de s’arrêter à cet endroit : un parcours qui continuerait enregistrerait plutôt le dernier jour plus chaud.

C’est lent lorsque les jours plus chauds sont éloignés ou inexistants. Si les 10^4 jours ont tous la même température, aucun parcours ne s’arrête tôt : le jour 0 vérifie 9,999 jours, le jour 1 en vérifie 9,998, et le total est d’environ n²/2 = 5 × 10^7 comparaisons. Les parcours se chevauchent également : le jour 1 parcourt presque exactement le terrain déjà parcouru par le jour 0, sans rien en apprendre.

Algorithme

Créez un tableau de réponses rempli de zéros, avec une entrée par jour.
Pour chaque jour i, parcourez j de i+1 jusqu'au dernier jour.
Au premier j tel que temperatures[j] > temperatures[i], stockez j-i et arrêtez le parcours.
Retournez le tableau de réponses ; les jours pour lesquels le parcours n'a rien trouvé conservent la valeur 0.

def dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n
    for i in range(n):
        for j in range(i + 1, n):
            if temperatures[j] > temperatures[i]:
                answer[i] = j - i  # the first warmer day, so stop here
                break
    return answer

Pile monotone des jours d’attente

Intuition

Inversez le raisonnement. Au lieu de demander chaque jour ce qui vient après lui, parcourez les jours une fois et laissez chaque nouveau jour répondre aux jours précédents qu’il dépasse. Gardez les jours qui n’ont pas encore de réponse sur une pile, sous forme d’indices. Quand le jour présent arrive, tous les jours en attente qui sont plus froids que lui ont trouvé leur premier jour plus chaud : aujourd’hui. Retirez-les tous et écrivez today - day comme réponse. Empilez ensuite le jour présent, qui attend à son tour son propre jour plus chaud.

Parcourez [71, 69, 72, 70, 70, 75, 68]. Le jour 0 (71) est empilé. Le jour 1 (69) n’est pas plus chaud que 71, alors il est empilé au-dessus : la pile contient les jours [0, 1]. Le jour 2 (72) retire le jour 1 (attente de 1), puis le jour 0 (attente de 2), et est empilé. Les jours 3 et 4 (70 et 70) sont empilés ; le second 70 ne retire pas le premier, car une température égale n’est pas plus chaude. Le jour 5 (75) retire le jour 4 (attente de 1), le jour 3 (attente de 2), puis le jour 2 (attente de 3). Le jour 6 (68) est empilé. Les jours 5 et 6 sont toujours en attente à la fin, donc leur réponse reste 0. La réponse est [2, 1, 3, 2, 1, 0, 0].

Pourquoi seul le sommet compte : les températures de la pile ne montent jamais de bas en haut. Un jour n’est empilé qu’après le retrait de tous les jours plus froids qui se trouvaient au-dessus de lui ; tout ce qui se trouve en dessous est donc au moins aussi chaud. Si le jour présent n’est pas plus chaud que le sommet, il n’est pas non plus plus chaud que les jours en dessous, et vous pouvez arrêter de retirer des éléments. Un jour quitte la pile dès que le premier jour plus chaud apparaît : l’attente enregistrée correspond donc au premier jour plus chaud, et non au plus chaud.

La pile contient des indices, et non des températures, parce que la réponse est une distance et que vous devez savoir quelle entrée de la réponse remplir. Récupérez la température avec temperatures[day]. Chaque jour est empilé une fois et retiré au plus une fois. Le nombre total de retraits sur tout le parcours est donc au plus n, et le temps total est de O(n), même si un jour peut en retirer plusieurs.

Algorithme

Crée un tableau de réponses rempli de zéros et une pile d’indices vide.
Pour chaque jour today, tant que le jour au sommet de la pile est plus froid qu’aujourd’hui, dépile-le et définis sa réponse comme today moins son indice.
Empile today.
Après la boucle, les jours encore dans la pile n’ont pas de jour plus chaud et conservent 0. Renvoie le tableau de réponses.

def dailyTemperatures(temperatures):
    answer = [0] * len(temperatures)
    waiting = []  # indices of days with no warmer day yet, colder toward the top
    for today, temp in enumerate(temperatures):
        # Today is the first warmer day for every colder day on top of the stack.
        while waiting and temperatures[waiting[-1]] < temp:
            day = waiting.pop()
            answer[day] = today - day
        waiting.append(today)
    # Days still waiting never get a warmer day and keep their 0.
    return answer

Pièges et cas limites

La boucle avec la pile ne comporte que quelques lignes ; les bogues se cachent dans la comparaison et dans ce que contient la pile.

Dépiler avec >= au lieu de >. Une journée avec la même température n’est pas plus chaude. Dans [71, 69, 72, 70, 70, 75, 68], le jour 3 attend 2 jours pour atteindre 75, et non 1 jour pour atteindre le deuxième 70.
Empiler les températures au lieu des indices. La réponse est une distance en jours ; tu as besoin de l’indice pour la calculer et pour savoir quelle entrée remplir.
Utiliser if quand tu as besoin de while. Une seule journée chaude peut répondre à plusieurs journées d’attente à la fois : dans le premier exemple, 75 répond à trois d’entre elles.
Renvoyer la température plus élevée ou l’indice du jour le plus chaud. Le résultat correspond au nombre de jours d’attente, j-i.
Laisser sans valeur les jours qui sont encore dans la pile. Leur réponse est 0 ; en C, alloue le tableau des réponses avec calloc ou remplis-le, car la mémoire de malloc contient des valeurs indéterminées.
Laisser le parcours vers l’avant dépasser le premier jour plus chaud. Sans le break, il enregistre le dernier jour plus chaud au lieu du premier.

Questions fréquentes4

Quelle est la complexité temporelle de Daily Temperatures ?

La solution avec une pile monotone s’exécute en O(n) temps et utilise O(n) d’espace supplémentaire. Chaque jour est empilé une fois et dépilé au plus une fois, donc la boucle interne s’exécute au plus n fois sur l’ensemble du parcours. Parcourir les jours suivants à partir de chaque jour prend un temps de O(n²), soit environ 5 × 10^7 comparaisons pour 10^4 jours sans journée plus chaude.

Pourquoi la pile stocke-t-elle des indices plutôt que des températures ?

La réponse pour un jour est une distance, today - day ; tu as donc besoin de la position du jour. L’indice t’indique également quelle entrée du tableau de réponses remplir lorsque le jour est retiré. La température est accessible en une seule consultation avec temperatures[day], donc la stocker aussi n’apporte rien.

Peut-on résoudre Daily Temperatures sans pile ?

Oui. Parcours les jours du dernier au premier et, pour le jour i, commence à j = i+1. Tant que le jour j n’est pas plus chaud, passe au jour indiqué par la réponse pour j, j + answer[j] ; si answer[j] vaut 0, aucun jour plus chaud n’existe et le jour i reçoit également 0. Les sauts ignorent tous les jours qui ne peuvent pas être la réponse, chaque jour est ignoré au plus une fois, et la complexité temporelle reste O(n), sans autre mémoire que le tableau des réponses.

Quel est le lien entre Daily Temperatures et Next Greater Element ?

C’est la même question posée pour chaque position : trouver la prochaine valeur plus grande à droite. Next Greater Element renvoie cette valeur ; Daily Temperatures renvoie la distance qui la sépare, c’est pourquoi la pile contient des indices. La même pile monotone, inversée pour dépiler lorsqu’une valeur plus petite apparaît, répond aussi aux questions sur le prochain élément plus petit.

Python

def dailyTemperatures(temperatures):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

temperatures = [71, 69, 72, 70, 70, 75, 68]

Attendu

[2, 1, 3, 2, 1, 0, 0]