algorithm
Algoritmo de ventana deslizante

Algoritmo de ventana deslizante Información básica

El algoritmo de la ventana deslizante se utiliza para realizar la operación requerida en un tamaño de ventana específico de un gran búfer o conjunto dado. La ventana comienza desde el primer elemento y sigue desplazándose hacia la derecha un elemento. El objetivo es encontrar los k números mínimos presentes en cada ventana. Esto se conoce comúnmente como problema de ventana deslizante o algoritmo.

Por ejemplo, para encontrar el elemento máximo o mínimo de cada elemento n en una matriz dada, se utiliza el algoritmo de ventana deslizante.

Ejemplo:

Matriz de entrada: [1 3 -1 -3 5 3 6 7]

Tamaño de la ventana: 3

Elemento máximo de cada elemento 3 de la matriz de entrada:

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

Elemento mínimo de cada 3 elementos de la matriz de entrada:

+---------------------------------+---------+
|      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étodos para encontrar la suma de 3 elementos:

Método 1:

La primera forma es usar la clasificación rápida, cuando el pivote está en la posición Kth, todos los elementos en el lado derecho son mayores que el pivote, por lo tanto, todos los elementos en el lado izquierdo se convierten automáticamente en los elementos más pequeños de la matriz dada.

Método 2:

Mantenga una matriz de elementos K, llénela con los primeros K elementos de la matriz de entrada dada. Ahora, desde el elemento K + 1, verifique si el elemento actual es menor que el elemento máximo en la matriz auxiliar, en caso afirmativo, agregue este elemento a la matriz. El único problema con la solución anterior es que debemos realizar un seguimiento del elemento máximo. Aún es factible. ¿Cómo podemos realizar un seguimiento del elemento máximo en conjunto de entero? Piense montón. Piensa en el montón de Max.

Método 3:

¡Genial! En O (1) obtendríamos el elemento máximo entre los elementos K ya elegidos como los elementos K más pequeños. Si el máximo en el conjunto actual es mayor que el elemento recientemente considerado, debemos eliminar el máximo e introducir un nuevo elemento en el conjunto del K elemento más pequeño. Heapify nuevamente para mantener la propiedad del montón. Ahora podemos obtener fácilmente K elementos mínimos en la matriz de N.

Espacio auxiliar: O(n)

Complejidad del tiempo: O(n)

Implementación del algoritmo de ventana deslizante 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);
    }
}