algorithm
Algorithme de fenêtre coulissante

Algorithme de fenêtre coulissante Informations de base

L'algorithme de fenêtre glissante est utilisé pour effectuer les opérations requises sur une taille de fenêtre spécifique d'un grand tampon ou d'un tableau donné. La fenêtre part du 1er élément et continue de se déplacer d'un élément à l'autre. L'objectif est de trouver le nombre minimal de k présent dans chaque fenêtre. Ceci est communément appelé problème de fenêtre coulissante ou algorithme.

Par exemple, pour trouver l'élément maximal ou minimal de chaque élément n dans un tableau donné, un algorithme de fenêtre glissante est utilisé.

Exemple:

Tableau d'entrée: [1 3 -1 -3 5 3 6 7]

Taille de la fenêtre: 3

Elément maximum de tous les 3 éléments du tableau d'entrée:

+---------------------------------+---------+
|      Windows Position           |   Max   |
+------------+----+---+---+---+---+---------+
|[1   3   -1]| -3 | 5 | 3 | 6 | 7 |    3    |
+------------+----+---+---+---+---+---------+
| 1 |[3   -1   -3]| 5 | 3 | 6 | 7 |    3    |
+---+-------------+---+---+---+---+---------+
| 1 | 3 |[-1   -3   5]| 3 | 6 | 7 |    5    |
+---+---+-------------+---+---+---+---------+
| 1 | 3 | -1 |[-3   5   3]| 6 | 7 |    5    |
+---+---+----+------------+---+---+---------+
| 1 | 3 | -1 | -3 |[5   3   6]| 7 |    6    |
+---+---+----+----+-----------+---+---------+
| 1 | 3 | -1 | -3 | 5 |[3   6   7]|    7    |
+---+---+----+----+---+-----------+---------+

Elément minimum pour chaque élément du tableau d'entrée:

+---------------------------------+---------+
|      Windows Position           |   Min   |
+------------+----+---+---+---+---+---------+
|[1   3   -1]| -3 | 5 | 3 | 6 | 7 |   -1    |
+------------+----+---+---+---+---+---------+
| 1 |[3   -1   -3]| 5 | 3 | 6 | 7 |   -3    |
+---+-------------+---+---+---+---+---------+
| 1 | 3 |[-1   -3   5]| 3 | 6 | 7 |   -3    |
+---+---+-------------+---+---+---+---------+
| 1 | 3 | -1 |[-3   5   3]| 6 | 7 |   -3    |
+---+---+----+------------+---+---+---------+
| 1 | 3 | -1 | -3 |[5   3   6]| 7 |    3    |
+---+---+----+----+-----------+---+---------+
| 1 | 3 | -1 | -3 | 5 |[3   6   7]|    3    |
+---+---+----+----+---+-----------+---------+

Méthodes pour trouver la somme de 3 éléments:

Méthode 1:

La première méthode consiste à utiliser le tri rapide, lorsque le pivot est à la position K, tous les éléments du côté droit sont supérieurs au pivot, par conséquent, tous les éléments du côté gauche deviennent automatiquement les plus petits éléments d’un tableau donné.

Méthode 2:

Conservez un tableau d'éléments K, remplissez-le avec les premiers K éléments d'un tableau d'entrée donné. Maintenant, à partir de l'élément K + 1, vérifiez si l'élément actuel est inférieur à l'élément maximal du tableau auxiliaire, si oui, ajoutez cet élément dans le tableau. Le seul problème avec la solution ci-dessus est que nous devons garder la trace de l'élément maximum. Toujours réalisable. Comment pouvons-nous garder trace de l'élément maximum dans l'ensemble des nombres entiers? Pensez tas Pensez Max tas.

Méthode 3:

Génial! Dans O (1), on obtiendrait l'élément max parmi K éléments déjà choisis comme plus petits éléments K. Si max dans l'ensemble actuel est supérieur à l'élément nouvellement considéré, nous devons supprimer max et introduire un nouvel élément dans l'ensemble du plus petit élément K. Heapify à nouveau pour conserver la propriété heap. Maintenant, nous pouvons facilement obtenir K éléments minimum dans le tableau de N.

Espace auxiliaire: O(n)

Complexité temporelle: O(n)

Implémentation de l'algorithme de fenêtre coulissante en C #

public class SlidingWindow
{
    public static int[] MaxSlidingWindow(int[] input, int k)
    {
        int[] result = new int[input.Length - k + 1];
        for (int i = 0; i <= input.Length - k; i++)
        {
            var max = input[i];
            for (int j = 1; j < k; j++)
            {
                if (input[i + j] > max) max = input[i + j];
            }
            result[i] = max;
        }
        return result;
    }

    public static int[] MinSlidingWindow(int[] input, int k)
    {
        int[] result = new int[input.Length - k + 1];
        for (int i = 0; i <= input.Length - k; i++)
        {
            var min = input[i];
            for (int j = 1; j < k; j++)
            {
                if (input[i + j] < min) min = input[i + j];
            }
            result[i] = min;
        }
        return result;
    }

    public static int[] MainMax(int[] input, int n)
    {
        return MaxSlidingWindow(input, n);
    }

    public static int[] MainMin(int[] input, int n)
    {
        return MinSlidingWindow(input, n);
    }
}