algorithm
Algorytm okna przesuwnego

Algorytm przesuwanego okna Podstawowe informacje

Algorytm przesuwania okna służy do wykonywania wymaganej operacji na określonym rozmiarze okna danego dużego bufora lub tablicy. Okno zaczyna się od pierwszego elementu i przesuwa się w prawo o jeden element. Celem jest znalezienie minimalnej liczby k obecnych w każdym oknie. Jest to powszechnie znane jako problem lub algorytm przesuwanego okna.

Na przykład, aby znaleźć maksymalny lub minimalny element z każdego n elementu w danej tablicy, stosuje się algorytm przesuwanego okna.

Przykład:

Tablica wejściowa: [1 3 -1-3 5 3 6 7]

Rozmiar okna: 3

Maksymalny element z każdego 3 elementu tablicy wejściowej:

+---------------------------------+---------+
|      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    |
+---+---+----+----+---+-----------+---------+

Minimalny element z każdego 3 elementu tablicy wejściowej:

+---------------------------------+---------+
|      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    |
+---+---+----+----+---+-----------+---------+

Metody znajdowania sumy 3 elementów:

Metoda 1:

Pierwszym sposobem jest użycie szybkiego sortowania, gdy element przestawny znajduje się w pozycji Kth, wszystkie elementy po prawej stronie są większe niż pivot, dlatego wszystkie elementy po lewej stronie automatycznie stają się K najmniejszymi elementami danej tablicy.

Metoda 2:

Zachowaj tablicę K elementów, wypełnij ją pierwszymi K elementami danej tablicy wejściowej. Teraz z elementu K + 1 sprawdź, czy bieżący element jest mniejszy niż maksymalny element w tablicy pomocniczej, jeśli tak, dodaj ten element do tablicy. Jedynym problemem związanym z powyższym rozwiązaniem jest to, że musimy śledzić maksymalny element. Nadal wykonalne. Jak możemy śledzić maksymalny element w zestawie liczb całkowitych? Pomyśl o kupie. Pomyśl o kupie Max.

Metoda 3:

Świetny! W O (1) otrzymalibyśmy maksymalny element spośród K elementów już wybranych jako najmniejszych K. Jeśli maksimum w bieżącym zestawie jest większe niż nowo rozważany element, musimy usunąć maksimum i wprowadzić nowy element w zestawie K najmniejszego elementu. Heapify ponownie, aby zachować właściwość sterty. Teraz możemy łatwo uzyskać K minimum elementów w tablicy N.

Space Auxiliary: O(n)

Złożoność czasu: O(n)

Implementacja algorytmu przesuwanego okna w 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);
    }
}