Gymnastique algorithmique 2

Find Maximum in Sliding Window

La description

Étant donné un tableau d'entiers et une fenêtre de taille w, trouve la valeur maximale actuelle dans la fenêtre lorsque la fenêtre (partie du tableau) glisse à travers le tableau.

Exemple

Avec une taille de fenêtre de 3, trouvons tous les maximums en glissant.

step1 La valeur maximale parmi les trois éléments de Window est 2

step2 Décaler de un, la valeur maximale parmi les trois éléments de Window est 3

step3 Décaler de un, la valeur maximale parmi les trois éléments de Window est 6

Enfin, la structure de données contenant 2, 3 et 6 doit être renvoyée.

Solution

Time Complexity: O(n) Tous les éléments sont poussés et sortis de deque une seule fois en une seule analyse. Push et pop sont O (1), donc L'algorithme fonctionne avec la complexité temporelle O (n).

Space Complexity: O(w) La complexité de l'espace est O (w) car elle utilise une liste de tailles de fenêtre.

Flux d'algorithme approximatif

Cet algorithme utilise la structure de données deque pour trouver la valeur maximale dans la fenêtre. Le but de l'utilisation de cette structure de données est de pousser et d'afficher des opérations telles que l'ajout et la suppression de données aux deux extrémités. C'est parce que les deux extrémités des files d'attente fonctionnent avec O (1). Cela agit comme une fenêtre. Il y a deux points à noter ici.

1. Mettez l'index de l'élément, et non l'élément du tableau, dans le deque.
2. Mettez l'index maximum au début de deque et les autres index à la fin.

Au début de l'algorithme, deque est de la merde, alors ajoutez l'index de l'élément par la taille de la première fenêtre.

Si l'élément que vous ajoutez est plus petit que l'élément après le deque, l'élément ajouté sera le dernier élément du nouveau deque. Si l'élément à ajouter est plus grand, faites sauter l'élément à plusieurs reprises derrière le deque jusqu'à ce qu'un élément plus grand soit trouvé. Poussez le nouvel élément que vous souhaitez ajouter comme fin.

Comme vous pouvez le voir, deque stocke les éléments dans l'ordre décroissant. Le début de la deque contient l'index de la valeur maximale pour cette fenêtre particulière.

Répétez les étapes suivantes à chaque fois que la fenêtre se déplace vers la droite.

1. Si l'élément derrière le deque est inférieur ou égal à l'élément courant à ajouter, supprimez l'élément du deque jusqu'à ce que l'index de l'élément plus grand que l'élément à ajouter apparaisse.
2. Si vous déplacez une fenêtre et que la valeur ne rentre pas dans la fenêtre courante, le premier index d'élément est supprimé.
3. Poussez l'index de l'élément courant derrière la fenêtre.

Code