algorithm
Алгоритм раздвижного окна

Алгоритм скользящего окна Основная информация

Алгоритм скользящего окна используется для выполнения требуемой операции для конкретного размера окна заданного большого буфера или массива. Окно начинается с 1-го элемента и смещается справа на один элемент. Цель состоит в том, чтобы найти минимальные k чисел, присутствующих в каждом окне. Это обычно известно как проблема или алгоритм раздвижного окна.

Например, чтобы найти максимальный или минимальный элемент из каждого n элемента в заданном массиве, используется алгоритм скользящего окна.

Пример:

Входной массив: [1 3 -1 -3 5 3 6 7]

Размер окна: 3

Максимальный элемент из каждых 3 элементов входного массива:

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

Минимальный элемент из каждых 3 элементов входного массива:

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

Методы для нахождения суммы 3 элемента:

Способ 1:

Первый способ - использовать быструю сортировку, когда точка поворота находится в позиции Kth, все элементы с правой стороны больше, чем точка поворота, поэтому все элементы с левой стороны автоматически становятся K наименьшими элементами заданного массива.

Способ 2:

Храните массив элементов K, заполните его с помощью первых элементов K данного массива ввода. Теперь из элемента K + 1 проверьте, является ли текущий элемент меньше максимального элемента во вспомогательном массиве, если да, добавьте этот элемент в массив. Единственная проблема с вышеупомянутым решением заключается в том, что нам нужно отслеживать максимальный элемент. Все еще работоспособно. Как мы можем отслеживать максимальный элемент в наборе integer? Подумайте, куча. Подумайте, Макс куча.

Способ 3:

Большой! В O (1) мы получили бы максимальный элемент среди K элементов, которые были выбраны как самые маленькие K-элементы. Если max в текущем наборе больше, чем новый элемент, нам нужно удалить max и ввести новый элемент в множество наименьшего элемента K. Heapify снова, чтобы сохранить свойство кучи. Теперь мы можем легко получить K минимальных элементов в массиве N.

Вспомогательный объем: O(n)

Сложность времени: O(n)

Реализация алгоритма раздвижного окна в 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);
    }
}