Sliding Window Maximum

Q: Quelle est la complexité temporelle du maximum de fenêtre glissante ?

La solution avec une deque monotone s’exécute en temps O(n) . Chaque indice est ajouté une fois et retiré au plus une fois ; la boucle interne effectue donc au plus n retraits sur l’ensemble de l’exécution, même si une seule étape peut en effectuer plusieurs. La deque contient au plus k indices, l’espace supplémentaire est donc de O(k) , en plus du résultat.

DifficileFenêtre glissante Pile monotone File

+10

Vous recevez un tableau d’entiers nums et une taille de fenêtre k. Une fenêtre couvre k valeurs consécutives. Elle commence à l’extrémité gauche du tableau et se déplace d’une position vers la droite à chaque fois, jusqu’à ce que son bord droit atteigne la dernière valeur.

Renvoyez un tableau contenant la plus grande valeur dans la fenêtre à chacune de ses positions, de gauche à droite. Un tableau de longueur n comporte n-k+1 fenêtres, le résultat contient donc n-k+1 valeurs.

Fonction

maxSlidingWindow(nums: integer-array, k: integer) → integer-array

numsinteger-array: le tableau sur lequel la fenêtre se déplace
kinteger: le nombre de valeurs dans chaque fenêtre
Renvoieinteger-array: la valeur la plus grande de chaque fenêtre, de la fenêtre la plus à gauche à la plus à droite

Contraintes

1 ≤ k ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
Le résultat contient nums.length-k+1 valeurs, une par fenêtre, de gauche à droite.

Exemples

Entrée: nums = [4, 2, 12, 3, 8, 5, 1]k = 3
Sortie: [12, 12, 12, 8, 8]
Explication: 12 se trouve dans les trois premières fenêtres, [4, 2, 12], [2, 12, 3] et [12, 3, 8]. Après sa sortie, les fenêtres [3, 8, 5] et [8, 5, 1] ont toutes deux 8 comme valeur maximale.

Entrée: nums = [-3, -1, -7, -2]k = 2
Sortie: [-1, -1, -2]
Explication: Les fenêtres sont [-3, -1], [-1, -7] et [-7, -2]. Le plus grand de deux nombres négatifs est celui qui est le plus proche de zéro, ce qui donne -1, -1 et -2.

Entrée: nums = [6, 6, 1]k = 3
Sortie: [6]
Explication: Lorsque k est égal à la longueur du tableau, il y a une seule fenêtre : le tableau entier. Sa plus grande valeur est 6, et la deuxième occurrence de 6 ne donne pas une deuxième réponse.

+15 tests cachés à la soumission

Pour aller plus loin

Peux-tu construire une file qui permet d’ajouter une valeur à l’arrière, de retirer la valeur à l’avant et de lire son maximum actuel, chaque opération ayant un temps amorti de O(1) ?

Indices

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

0 sur 3 ouverts

Solution

Les fenêtres voisines partagent k-1 valeurs, donc calculer chaque maximum à partir de zéro répète presque tout le travail. La difficulté, c’est qu’on ne peut pas annuler un maximum : lorsque la plus grande valeur sort par la gauche, il faut trouver la suivante sans relire la fenêtre. Une deque monotone conserve exactement les valeurs qui pourraient encore devenir un maximum, dans l’ordre, de sorte que la réponse se trouve toujours à son début et que chaque indice y entre et en sort une seule fois.

Parcourir chaque fenêtre

Correcte, mais ne termine pas sur les plus gros tests

Intuition

L’idée la plus directe découle de l’énoncé. La fenêtre qui commence à l’indice start couvre les indices de start à start+k-1. Lisez ces k valeurs, conservez la plus grande, puis décalez le début d’un pas vers la droite. Il y a n-k+1 positions de départ, de 0 à n-k.

C’est correct par définition : chaque fenêtre est parcourue en entier, donc sa valeur maximale ne peut pas être manquée. La mémoire supplémentaire se limite à une variable pour le maximum courant, en plus du résultat.

C’est lent. Chacune des n-k+1 fenêtres nécessite k lectures, et le produit est maximal lorsque k vaut environ la moitié de n. Avec n = 2 × 10^4 et k = 10^4, cela représente 10^4 fenêtres de 10^4 valeurs, soit 10^8 lectures. Pire encore, deux fenêtres voisines partagent k-1 valeurs, donc presque chaque lecture répète une lecture déjà effectuée.

Algorithme

Créez une liste de résultats vide.
Parcourez start de 0 à n-k.
Définissez best sur nums[start], puis comparez-le à chaque valeur jusqu’à nums[start+k-1] et conservez la plus grande.
Ajoutez best au résultat.
Retournez le résultat.

def maxSlidingWindow(nums, k):
    result = []
    for start in range(len(nums) - k + 1):
        # Read all k values of this window again
        result.append(max(nums[i] for i in range(start, start + k)))
    return result

Blocs avec des maxima de chaque côté

Intuition

Découpe le tableau en blocs de k : indices 0 à k-1, puis k à 2k-1, et ainsi de suite, avec un dernier bloc plus court si n n’est pas un multiple de k. Une fenêtre a exactement une longueur de k, elle correspond donc à un bloc ou couvre la fin d’un bloc et le début du suivant. Elle ne touche jamais trois blocs.

On peut donc utiliser deux tableaux. fromStart[i] est la valeur maximale depuis le début du bloc de i jusqu’à i, calculée de gauche à droite et réinitialisée au début de chaque bloc. toEnd[i] est la valeur maximale de i jusqu’à la fin de son bloc, calculée de droite à gauche et réinitialisée à la fin de chaque bloc. La fenêtre qui commence à i se termine à i+k-1. Sa partie gauche est couverte par toEnd[i] et sa partie droite par fromStart[i+k-1] ; son maximum est donc le plus grand des deux. Lorsque la fenêtre correspond à un bloc entier, les deux parties donnent le maximum de ce bloc, et la réponse est donc toujours correcte.

Avec nums = [4, 2, 12, 3, 8, 5, 1] et k = 3, les blocs sont [4, 2, 12], [3, 8, 5] et [1]. fromStart vaut [4, 4, 12, 3, 8, 8, 1] et toEnd vaut [12, 12, 12, 8, 8, 5, 1]. La fenêtre [2, 12, 3] commence à l’indice 1 : toEnd[1] = 12 couvre 2 et 12, fromStart[3] = 3 couvre 3, et la réponse est 12.

Cette méthode s’exécute en O(n), avec trois parcours du tableau. Son coût : deux tableaux auxiliaires de longueur n, et elle nécessite le tableau entier avant de pouvoir répondre pour la première fenêtre.

Algorithme

Remplissez fromStart de gauche à droite : copiez nums[i] lorsque i est un multiple de k, sinon prenez la plus grande valeur entre fromStart[i-1] et nums[i].
Remplissez toEnd de droite à gauche : copiez nums[i] lorsque i est le dernier indice ou que i+1 est un multiple de k, sinon prenez la plus grande valeur entre toEnd[i+1] et nums[i].
Pour chaque début i de 0 à n-k, ajoutez la plus grande valeur entre toEnd[i] et fromStart[i+k-1].
Renvoyez le résultat.

def maxSlidingWindow(nums, k):
    n = len(nums)
    # Cut nums into blocks of k: indices 0..k-1, k..2k-1, and so on.
    from_start = [0] * n  # max from the start of i's block up to i
    to_end = [0] * n      # max from i up to the end of i's block
    for i in range(n):
        if i % k == 0:
            from_start[i] = nums[i]
        else:
            from_start[i] = max(from_start[i - 1], nums[i])
    for i in range(n - 1, -1, -1):
        if i == n - 1 or (i + 1) % k == 0:
            to_end[i] = nums[i]
        else:
            to_end[i] = max(to_end[i + 1], nums[i])
    # A window [i, i+k-1] is the tail of one block plus the head of the next.
    return [max(to_end[i], from_start[i + k - 1]) for i in range(n - k + 1)]

Deque monotone d’indices

Intuition

Partons d’une observation. Supposons que l’indice j précède l’indice i et que nums[j] ≤ nums[i]. Toute fenêtre ultérieure qui contient encore j contient aussi i, car i est plus à droite et en sort plus tard. Dans toutes ces fenêtres, nums[i] est au moins aussi grand, donc j ne peut plus jamais être le maximum. Dès que i arrive, j ne sert plus à rien et tu peux l’oublier.

Garde une double file des indices que tu n’as pas oubliés. Quand i arrive, retire de la fin les indices dont les valeurs sont inférieures ou égales à nums[i], puis ajoute i. Les indices restants ont alors des valeurs strictement décroissantes de l’avant vers l’arrière, puisque toute valeur plus ancienne qui n’était pas supérieure a été retirée. L’avant contient donc la valeur maximale de la fenêtre. La deque stocke des indices, et non des valeurs, car l’indice en tête doit aussi être retiré lorsque la fenêtre le dépasse : la fenêtre qui se termine à i commence à i-k+1, donc l’indice i-k est celui qui est sorti de la fenêtre et, s’il est en tête, tu le retires.

Suivons nums = [4, 2, 12, 3, 8, 5, 1] avec k = 3, en indiquant les valeurs dans la deque. 4 entre : [4]. 2 est plus petit, il attend donc derrière : [4, 2]. 12 retire les deux : [12], et la réponse de la première fenêtre est 12. 3 attend : [12, 3], réponse 12. 8 retire 3 : [12, 8], réponse 12. 5 attend : [12, 8, 5], mais 12 se trouve à l’indice 2, et la fenêtre qui se termine à l’indice 5 commence à l’indice 3, donc 12 est sorti de la fenêtre : [8, 5], réponse 8. 1 attend : [8, 5, 1], réponse 8.

Pourquoi c’est en O(n) : la boucle interne peut retirer plusieurs indices en une seule étape, mais chaque indice est ajouté une fois et retiré au plus une fois, soit de la fin lorsqu’une valeur plus grande le dépasse, soit de l’avant lorsqu’il sort de la fenêtre. Au total, toutes les suppressions de l’exécution représentent au plus n, donc le travail total correspond à au plus 2n opérations sur la deque. Chaque indice de la deque se trouve dans la fenêtre courante, elle ne contient donc jamais plus de k indices.

Algorithme

Créez un deque vide pour les indices et une liste de résultats vide.
Pour chaque indice i, retirez les indices de l’arrière tant que le deque n’est pas vide et que la valeur à son arrière est inférieure ou égale à nums[i].
Ajoutez i à l’arrière.
Si l’indice à l’avant est égal à i-k, il a quitté la fenêtre : retirez-le de l’avant.
Dès que i ≥ k-1, une fenêtre complète se termine à i : ajoutez à la liste des résultats la valeur correspondant à l’indice à l’avant.
Renvoyez la liste des résultats.

from collections import deque


def maxSlidingWindow(nums, k):
    window = deque()  # indices; their values strictly decrease from front to back
    result = []
    for i, x in enumerate(nums):
        # A value at the back that is not bigger than x can never be a maximum again.
        while window and nums[window[-1]] <= x:
            window.pop()
        window.append(i)
        # The front index has slid out of the window on the left.
        if window[0] == i - k:
            window.popleft()
        # From index k-1 on, every step completes a window; its maximum sits at the front.
        if i >= k - 1:
            result.append(nums[window[0]])
    return result

Pièges et cas limites

La plupart des bogues viennent des limites de la fenêtre ou de ce que stocke la deque.

Stocker des valeurs au lieu des indices. Tu supprimes alors l’élément en tête lorsqu’il est égal à nums[i-k], ce qui échoue en présence de doublons. Avec [3, 1, 3] et k = 2, le deuxième 3 supprime le premier, puis est lui-même supprimé, car il est égal à la valeur qui vient de sortir. Stocke les indices et compare l’élément en tête à i-k.
Donner la réponse trop tôt ou trop tard. La première fenêtre complète se termine à l’indice k-1, et non à k, et le résultat doit contenir exactement n-k+1 valeurs.
Supprimer le mauvais indice. La fenêtre qui se termine à i commence à i-k+1 : l’indice qui sort est donc i-k. Supprimer i-k+1 retire une valeur qui se trouve encore dans la fenêtre.
Lire l’élément en queue ou en tête d’une deque vide. Vérifie qu’elle contient quelque chose avant de comparer avec son élément en queue.
Considérer la deque comme une copie de la fenêtre. Elle ne contient que les candidats, soit de 1 à k indices, sa taille ne t’indique donc rien sur celle de la fenêtre.
Dans l’approche par blocs, oublier que le dernier bloc peut être plus court que k. Le parcours de droite à gauche doit recommencer au dernier indice ainsi qu’à la fin de chaque bloc.

Questions fréquentes4

Quelle est la complexité temporelle du maximum de fenêtre glissante ?

La solution avec une deque monotone s’exécute en temps O(n). Chaque indice est ajouté une fois et retiré au plus une fois ; la boucle interne effectue donc au plus n retraits sur l’ensemble de l’exécution, même si une seule étape peut en effectuer plusieurs. La deque contient au plus k indices, l’espace supplémentaire est donc de O(k), en plus du résultat.

Le maximum d’une fenêtre glissante peut-il être résolu avec un tas ?

Oui. Insérez des paires valeur-indice dans un tas max. Avant de lire l’élément au sommet, retirez-le tant que son indice est en dehors de la fenêtre, car les entrées obsolètes ne sont supprimées que lorsqu’elles atteignent le sommet. Cela s’exécute en O(n log n) et peut contenir jusqu’à n entrées. La deque est plus rapide et plus compacte, car elle supprime les valeurs inutiles dès qu’une plus grande arrive.

Pourquoi le deque stocke-t-il des indices et non des valeurs ?

L’élément en tête doit être retiré lorsque la fenêtre le dépasse, et seul son index vous l’indique. Avec les valeurs seules, vous devriez le deviner à partir de nums[i-k], ce qui échoue lorsque la même valeur apparaît plusieurs fois. L’index vous donne également la valeur sans coût supplémentaire, avec nums[index].

Quelle est la différence entre une deque monotone et une pile monotone ?

L’arrière du deque fonctionne comme une pile monotone : avant d’empiler une valeur, on dépile celles qu’elle rend inutiles. Le deque ajoute une seconde sortie à l’avant pour les valeurs trop anciennes. Un problème sans expiration, comme la recherche de l’élément suivant plus grand, ne nécessite que la pile ; une fenêtre glissante nécessite les deux extrémités. Inversez la comparaison et le même code donne le minimum de chaque fenêtre.

Python

def maxSlidingWindow(nums, k):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

nums = [4, 2, 12, 3, 8, 5, 1]
k = 3

Attendu

[12, 12, 12, 8, 8]

Sliding Window Maximum

Fonction

Contraintes

Exemples

Indices

Solution

Parcourir chaque fenêtre

Blocs avec des maxima de chaque côté

Deque monotone d’indices

Pièges et cas limites

Questions fréquentes4

Problèmes similaires