Daily Temperatures

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

La solution avec une pile monotone s’exécute en O(n) et utilise O(n) d’espace supplémentaire, car chaque jour est empilé une fois et dépilé au plus une fois. Parcourir les jours suivants à partir de chaque jour prend O(n²) , soit environ 5 × 10^7 comparaisons pour 10^4 jours sans jour plus chaud.

MoyenPile monotone

+10

temperatures[i] est la température du jour i. Pour chaque jour, compte le nombre de jours d’attente à partir de celui-ci avant qu’un jour strictement plus chaud n’arrive, ou 0 si aucun jour plus chaud ne vient ensuite. Retourne un tableau de même longueur dont 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 jusqu’à un jour plus chaud, ou 0 si aucun ne vient

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 (71) attend 2 jours pour 72. Le jour 3 (70) ignore le 70 égal du jour 4 et attend 2 jours pour 75. Rien après 75 ou 68 n’est plus chaud, donc les deux obtiennent 0.

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 coût ?

Solution

Un parcours vers l’avant à partir de chaque jour répète le travail et, lorsque les journées chaudes sont rares, chaque parcours va jusqu’au bout. À la place, parcourez les jours une seule fois et laissez chaque nouveau jour répondre aux jours précédents qu’il dépasse. Les jours qui attendent encore restent sur une pile dont les températures ne font qu’être décroissantes du bas vers le haut, si bien que toutes les réponses sont obtenues en un seul passage.

Parcourir vers l’avant à partir de chaque jour

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Pour le jour i, vérifie les jours i+1, i+2, et ainsi de suite, puis arrête-toi au premier jour strictement plus chaud j. La réponse est j-i, ou 0 si le parcours atteint la fin. En parcourant les jours dans l’ordre, le premier jour plus chaud rencontré est bien le premier qui existe.

Si les 10^4 jours ont tous la même température, aucun parcours ne s’arrête prématurément : environ n²/2 = 5 × 10^7 comparaisons, et le jour 1 parcourt presque le même chemin que le jour 0 a déjà parcouru.

Algorithme

Crée un tableau de réponses rempli de zéros, avec une entrée par jour.
Pour chaque jour i, parcours j de i+1 jusqu'au dernier jour.
Au premier j tel que temperatures[j] > temperatures[i], stocke j-i et arrête le parcours.
Retourne le tableau de réponses ; les jours pour lesquels le parcours n'a rien trouvé conservent 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

Garde sur une pile, sous forme d’indices, les jours qui n’ont pas encore de réponse. Quand aujourd’hui arrive, dépile chaque jour en attente plus froid qu’aujourd’hui : aujourd’hui est son premier jour plus chaud, donc sa réponse est today - day. Puis empile aujourd’hui.

Il suffit de vérifier le sommet. Un jour n’est empilé qu’après que tous les jours plus froids au-dessus de lui ont été dépilés ; les températures sur la pile ne montent donc jamais du bas vers le sommet. Si aujourd’hui n’est pas plus chaud que le sommet, il n’est plus chaud qu’aucun jour en dessous, et tu arrêtes de dépiler. Dans le premier exemple, le jour 5 (75) dépile les jours 4, 3 et 2, avec des attentes de 1, 2 et 3, tandis que le deuxième 70 n’a jamais dépilé le premier, car une température égale n’est pas plus chaude.

Chaque jour est empilé une fois et dépilé au plus une fois, donc le nombre total de dépilements est au plus n : O(n) en temps, même si un jour peut en dépiler beaucoup.

Algorithme

Crée un tableau de réponses rempli de zéros et une pile vide d’indices.
Pour chaque jour today, tant que le jour au sommet de la pile est plus froid que celui d’aujourd’hui, dépile-le et définis sa réponse comme la différence entre today et son indice.
Empile today.
Après la boucle, les jours encore dans la pile n’ont pas de jour plus chaud et conservent la valeur 0. Retourne 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

Retirer avec >= au lieu de >. Dans le premier exemple, le jour 3 attend alors 1 jour pour le deuxième 70 au lieu de 2 jours pour 75.
Empiler les températures au lieu des indices. Vous ne pouvez alors pas calculer la distance ni savoir quelle entrée de la réponse remplir.
Utiliser if là où vous avez besoin de while. Une journée chaude peut répondre à plusieurs jours d’attente : 75 répond à trois jours dans le premier exemple.
Laisser sans valeur les jours encore présents dans la pile. Leur réponse est 0 ; en C, allouez la réponse avec calloc, 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 à la place.

Questions fréquentes3

Quelle est la complexité temporelle de Daily Temperatures ?

La solution avec une pile monotone s’exécute en O(n) et utilise O(n) d’espace supplémentaire, car chaque jour est empilé une fois et dépilé au plus une fois. Parcourir les jours suivants à partir de chaque jour prend O(n²), soit environ 5 × 10^7 comparaisons pour 10^4 jours sans jour plus chaud.

Peut-on résoudre Daily Temperatures sans pile ?

Oui. Remplissez les réponses en remontant depuis le dernier jour, et pour le jour i, commencez à j = i+1 ; tant que le jour j n’est pas plus chaud, passez à j + answer[j], le jour qui répond à j. Si answer[j] vaut 0, le jour i reçoit aussi 0. Les sauts ignorent les jours qui ne peuvent pas répondre pour i : temps O(n), sans mémoire supplémentaire.

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 l’en sépare, raison pour laquelle la pile contient des indices. La même pile, inversée pour dépiler lorsqu’une valeur plus petite apparaît, répond aux questions sur l’élément suivant plus petit.

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

Test #1

Test #2

Test #3

Argument

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

Résultat attendu

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