Los problemas de ventana deslizante son problemas en los que una ventana de tamaño fijo o variable se mueve a través de una estructura de datos, generalmente una matriz o cadena, para resolver problemas de manera eficiente basados ​​en subconjuntos continuos de elementos. Esta técnica se utiliza cuando necesitamos encontrar subarreglos o subcadenas de acuerdo con un conjunto de condiciones determinado.

Técnica de ventana corredera

Tabla de contenidos

• ¿Qué es la técnica de la ventana corredera?
• ¿Cómo utilizar la técnica de la ventana corredera?
• Cómo identificar problemas con las ventanas corredizas
• Casos de uso de la técnica de ventana corrediza
• Problemas de práctica sobre la técnica de la ventana corrediza

¿Qué es la técnica de la ventana corredera?

Técnica de ventana corredera Es un método utilizado para resolver eficientemente problemas que implican definir un ventana o rango en los datos de entrada (matrices o cadenas) y luego mover esa ventana a través de los datos para realizar alguna operación dentro de la ventana. Esta técnica se usa comúnmente en algoritmos como encontrar subarreglos con una suma específica, encontrar la subcadena más larga con caracteres únicos o resolver problemas que requieren una ventana de tamaño fijo para procesar elementos de manera eficiente.

Tomemos un ejemplo para entender esto correctamente, digamos que tenemos una matriz de tamaño norte y también un número entero K. Ahora, tenemos que calcular la suma máxima de un subarreglo que tiene tamaño exactamente K. Ahora bien, ¿cómo deberíamos abordar este problema?

Una forma de hacer esto es tomar cada subarreglo de tamaño K de la matriz y encontrar la suma máxima de estos subarreglos. Esto se puede hacer usando bucles anidados que resultarán en O(N²) Complejidad del tiempo.

¿Pero podemos optimizar este enfoque?

La respuesta es Sí, en lugar de tomar cada k submatriz de tamaño K y calculando su suma, podemos simplemente tomar una submatriz de tamaño K del índice 0 a K-1 y calcular su suma. Ahora cambie nuestro rango uno por uno junto con las iteraciones y actualice el resultado, como en la siguiente iteración, aumente la izquierda y puntero derecho y actualice la suma anterior como se muestra en la siguiente imagen:

Técnica de ventana corredera

Ahora siga este método para cada iteración hasta llegar al final de la matriz:

Técnica de ventana corredera

cuantos ceros hay en mil millones

Entonces, podemos ver que en lugar de recalcular la suma de cada subarreglo de tamaño K, estamos usando la ventana anterior de tamaño K y usando sus resultados actualizamos la suma y desplazamos la ventana hacia la derecha moviendo los punteros izquierdo y derecho, esta operación es óptima porque Tómese O(1) tiempo para cambiar el rango en lugar de volver a calcularlo.

Este enfoque de cambiar los punteros y calcular los resultados en consecuencia se conoce como Técnica de ventana corredera .

¿Cómo utilizar la técnica de la ventana corredera?

Básicamente existen dos tipos de ventana corredera:

1. Ventana corrediza de tamaño fijo:

Los pasos generales para resolver estas preguntas son los siguientes:

• Encuentre el tamaño de la ventana requerida, digamos K.
• Calcule el resultado para la primera ventana, es decir, incluya los primeros K elementos de la estructura de datos.
• Luego use un bucle para deslizar la ventana 1 y siga calculando el resultado ventana por ventana.

2. Ventana corrediza de tamaño variable:

Los pasos generales para resolver estas preguntas son los siguientes:

• En este tipo de problema de ventana deslizante, aumentamos nuestro puntero derecho uno por uno hasta que nuestra condición sea verdadera.
• En cualquier paso, si nuestra condición no coincide, reducimos el tamaño de nuestra ventana aumentando el puntero izquierdo.
• Nuevamente, cuando nuestra condición se cumple, comenzamos a aumentar el puntero derecho y seguimos el paso 1.
• Seguimos estos pasos hasta llegar al final del array.

Cómo identificar problemas con las ventanas corredizas:

• Estos problemas generalmente requieren encontrar máximo/mínimo Submatriz , Subcadenas que satisfacen alguna condición específica.
• El tamaño del subarreglo o subcadena ' K' se dará en algunos de los problemas.
• Estos problemas se pueden resolver fácilmente en O(N²) complejidad del tiempo usando bucles anidados, usando una ventana deslizante podemos resolverlos en En) Complejidad del tiempo.
• Complejidad de tiempo requerida: O(N) u O(Nlog(N))
• Restricciones: norte <= 10⁶, Si N es el tamaño de la matriz/cadena.

Casos de uso de la técnica de ventana corrediza:

1. Para encontrar la suma máxima de todos los subarreglos de tamaño K:

Dada una serie de números enteros de tamaño 'norte', Nuestro objetivo es calcular la suma máxima de 'k' elementos consecutivos en la matriz.

Aporte : arreglo[] = {100, 200, 300, 400}, k = 2
Producción : 700

Aporte : arreglo[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}, k = 4
Producción : 39
Obtenemos la suma máxima sumando el subarreglo {4, 2, 10, 23} de tamaño 4.

Aporte : arreglo[] = {2, 3}, k = 3
Producción : Inválido
No hay ningún subarreglo de tamaño 3 ya que el tamaño de todo el arreglo es 2.

Enfoque ingenuo: Entonces, analicemos el problema con Enfoque de fuerza bruta . Comenzamos con el primer índice y sumamos hasta el kth elemento. Lo hacemos para todos los posibles bloques o grupos consecutivos de k elementos. Este método requiere un bucle for anidado, el bucle for externo comienza con el elemento inicial del bloque de k elementos, y el bucle interno o anidado se sumará hasta el k-ésimo elemento.

A continuación se muestra la implementación del enfoque anterior:

// O(n*k) solution for finding maximum sum of // a subarray of size k #include  using namespace std; // Returns maximum sum in a subarray of size k. int maxSum(int arr[], int n, int k) {  // Initialize result  int max_sum = INT_MIN;  // Consider all blocks starting with i.  for (int i = 0; i < n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = max(current_sum, max_sum);  }  return max_sum; } // Driver code int main() {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = sizeof(arr) / sizeof(arr[0]);  cout << maxSum(arr, n, k);  return 0; } // This code is contributed by Aditya Kumar (adityakumar129)>

// O(n*k) solution for finding maximum sum of // a subarray of size k #include  #include  #include  // Find maximum between two numbers. int max(int num1, int num2) {  return (num1>número2)? número1 : número2; } // Devuelve la suma máxima en un subarreglo de tamaño k. int maxSum(int arr[], int n, int k) { // Inicializar resultado int max_sum = INT_MIN;  // Considere todos los bloques que comienzan con i.  para (int i = 0; i< n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = max(current_sum, max_sum);  }  return max_sum; } // Driver code int main() {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = sizeof(arr) / sizeof(arr[0]);  printf('%d', maxSum(arr, n, k));  return 0; } // This code is contributed by Aditya Kumar (adityakumar129)>

// Java code O(n*k) solution for finding maximum sum of // a subarray of size k class GFG {  // Returns maximum sum in  // a subarray of size k.  static int maxSum(int arr[], int n, int k)  {  // Initialize result  int max_sum = Integer.MIN_VALUE;  // Consider all blocks starting with i.  for (int i = 0; i < n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = Math.max(current_sum, max_sum);  }  return max_sum;  }  // Driver code  public static void main(String[] args)  {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.length;  System.out.println(maxSum(arr, n, k));  } } // This code is contributed by Aditya Kumar (adityakumar129)>

# code import sys # O(n * k) solution for finding # maximum sum of a subarray of size k INT_MIN = -sys.maxsize - 1 # Returns maximum sum in a # subarray of size k. def maxSum(arr, n, k): # Initialize result max_sum = INT_MIN # Consider all blocks # starting with i. for i in range(n - k + 1): current_sum = 0 for j in range(k): current_sum = current_sum + arr[i + j] # Update result if required. max_sum = max(current_sum, max_sum) return max_sum # Driver code arr = [1, 4, 2, 10, 2, 3, 1, 0, 20] k = 4 n = len(arr) print(maxSum(arr, n, k)) # This code is contributed by mits>

// C# code here O(n*k) solution for // finding maximum sum of a subarray // of size k using System; class GFG {  // Returns maximum sum in a  // subarray of size k.  static int maxSum(int[] arr, int n, int k)  {  // Initialize result  int max_sum = int.MinValue;  // Consider all blocks starting  // with i.  for (int i = 0; i < n - k + 1; i++) {  int current_sum = 0;  for (int j = 0; j < k; j++)  current_sum = current_sum + arr[i + j];  // Update result if required.  max_sum = Math.Max(current_sum, max_sum);  }  return max_sum;  }  // Driver code  public static void Main()  {  int[] arr = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.Length;  Console.WriteLine(maxSum(arr, n, k));  } } // This code is contributed by anuj_67.>

function maxSum(arr, n, k) {  let max_sum = 0;    // Loop from i to k  for (let i = 0; i < k; i++) {  max_sum += arr[i];  }    let window_sum = max_sum;  for (let i = k; i < n; i++) {  window_sum = window_sum - arr[i - k] + arr[i];  max_sum = Math.max(max_sum, window_sum);  }  return max_sum; } // Driver code let arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]; let k = 4; let n = arr.length; console.log(maxSum(arr, n, k));>

 // code ?>// Solución O(n*k) para encontrar la suma máxima de // un subarreglo de tamaño k // Devuelve la suma máxima en un subarreglo de tamaño k. function maxSum($arr, $n, $k) { // Inicializa el resultado $max_sum = PHP_INT_MIN; // Considere todos los bloques // comenzando con i. para ( $i = 0; $i< $n - $k + 1; $i++) { $current_sum = 0; for ( $j = 0; $j < $k; $j++) $current_sum = $current_sum + $arr[$i + $j]; // Update result if required. $max_sum = max($current_sum, $max_sum ); } return $max_sum; } // Driver code $arr = array(1, 4, 2, 10, 2, 3, 1, 0, 20); $k = 4; $n = count($arr); echo maxSum($arr, $n, $k); // This code is contributed by anuj_67. ?>>

24>

Complejidad del tiempo: O(k*n) ya que contiene dos bucles anidados.
Espacio Auxiliar: O(1)

Aplicando la técnica de la ventana corredera:

• Calculamos la suma de los primeros k elementos de n términos usando un bucle lineal y almacenamos la suma en una variable suma_ventana .
• Luego recorreremos linealmente la matriz hasta que llegue al final y simultáneamente realizaremos un seguimiento de la suma máxima.
• Para obtener la suma actual de un bloque de k elementos simplemente reste el primer elemento del bloque anterior y agregue el último elemento del bloque actual.

La siguiente representación dejará claro cómo se desliza la ventana sobre la matriz.

Considere una matriz llegar[] = {5, 2, -1, 0, 3} y valor de k = 3 y norte = 5

Esta es la fase inicial en la que hemos calculado la suma de la ventana inicial a partir del índice 0. En esta etapa, la suma de la ventana es 6. Ahora, configuramos la suma_máxima como ventana_actual, es decir, 6.

Ahora, deslizamos nuestra ventana por un índice unitario. Por lo tanto, ahora descarta 5 de la ventana y agrega 0 a la ventana. Por lo tanto, obtendremos la suma de nuestra nueva ventana restándole 5 y luego sumándole 0. Entonces, la suma de nuestra ventana ahora se convierte en 1. Ahora, compararemos la suma de esta ventana con la suma_máxima. Como es más pequeño, no cambiaremos la suma_máxima.

De manera similar, ahora una vez más deslizamos nuestra ventana por un índice unitario y obtenemos que la suma de la nueva ventana sea 2. Nuevamente verificamos si la suma de la ventana actual es mayor que la suma_máxima hasta ahora. Una vez más, es más pequeño, por lo que no cambiamos la suma_máxima.
Por lo tanto, para la matriz anterior nuestra suma_máxima es 6.

A continuación se muestra el código para el enfoque anterior:

// O(n) solution for finding maximum sum of // a subarray of size k #include  using namespace std; // Returns maximum sum in a subarray of size k. int maxSum(int arr[], int n, int k) {  // n must be greater  if (n <= k) {  cout << 'Invalid';  return -1;  }  // Compute sum of first window of size k  int max_sum = 0;  for (int i = 0; i < k; i++)  max_sum += arr[i];  // Compute sums of remaining windows by  // removing first element of previous  // window and adding last element of  // current window.  int window_sum = max_sum;  for (int i = k; i < n; i++) {  window_sum += arr[i] - arr[i - k];  max_sum = max(max_sum, window_sum);  }  return max_sum; } // Driver code int main() {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = sizeof(arr) / sizeof(arr[0]);  cout << maxSum(arr, n, k);  return 0; }>

// Java code for // O(n) solution for finding // maximum sum of a subarray // of size k class GFG {  // Returns maximum sum in  // a subarray of size k.  static int maxSum(int arr[], int n, int k)  {  // n must be greater  if (n <= k) {  System.out.println('Invalid');  return -1;  }  // Compute sum of first window of size k  int max_sum = 0;  for (int i = 0; i < k; i++)  max_sum += arr[i];  // Compute sums of remaining windows by  // removing first element of previous  // window and adding last element of  // current window.  int window_sum = max_sum;  for (int i = k; i < n; i++) {  window_sum += arr[i] - arr[i - k];  max_sum = Math.max(max_sum, window_sum);  }  return max_sum;  }  // Driver code  public static void main(String[] args)  {  int arr[] = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.length;  System.out.println(maxSum(arr, n, k));  } } // This code is contributed // by prerna saini.>

# O(n) solution for finding # maximum sum of a subarray of size k def maxSum(arr, k): # length of the array n = len(arr) # n must be greater than k if n <= k: print('Invalid') return -1 # Compute sum of first window of size k window_sum = sum(arr[:k]) # first sum available max_sum = window_sum # Compute the sums of remaining windows by # removing first element of previous # window and adding last element of # the current window. for i in range(n - k): window_sum = window_sum - arr[i] + arr[i + k] max_sum = max(window_sum, max_sum) return max_sum # Driver code arr = [1, 4, 2, 10, 2, 3, 1, 0, 20] k = 4 print(maxSum(arr, k)) # This code is contributed by Kyle McClay>

// C# code for O(n) solution for finding // maximum sum of a subarray of size k using System; class GFG {  // Returns maximum sum in  // a subarray of size k.  static int maxSum(int[] arr, int n, int k)  {  // n must be greater  if (n <= k) {  Console.WriteLine('Invalid');  return -1;  }  // Compute sum of first window of size k  int max_sum = 0;  for (int i = 0; i < k; i++)  max_sum += arr[i];  // Compute sums of remaining windows by  // removing first element of previous  // window and adding last element of  // current window.  int window_sum = max_sum;  for (int i = k; i < n; i++) {  window_sum += arr[i] - arr[i - k];  max_sum = Math.Max(max_sum, window_sum);  }  return max_sum;  }  // Driver code  public static void Main()  {  int[] arr = { 1, 4, 2, 10, 2, 3, 1, 0, 20 };  int k = 4;  int n = arr.Length;  Console.WriteLine(maxSum(arr, n, k));  } } // This code is contributed by anuj_67.>

>

 // O(n) solution for finding maximum sum of // a subarray of size k // Returns maximum sum in a  // subarray of size k. function maxSum( $arr, $n, $k) { // n must be greater if ($n <= $k) { echo 'Invalid'; return -1; } // Compute sum of first // window of size k $max_sum = 0; for($i = 0; $i < $k; $i++) $max_sum += $arr[$i]; // Compute sums of remaining windows by // removing first element of previous // window and adding last element of // current window. $window_sum = $max_sum; for ($i = $k; $i < $n; $i++) { $window_sum += $arr[$i] - $arr[$i - $k]; $max_sum = max($max_sum, $window_sum); } return $max_sum; } // Driver code $arr = array(1, 4, 2, 10, 2, 3, 1, 0, 20); $k = 4; $n = count($arr); echo maxSum($arr, $n, $k); // This code is contributed by anuj_67 ?>>

24>

Complejidad del tiempo: En dónde norte es el tamaño de la matriz de entrada llegar[] .
Espacio Auxiliar: O(1)

2. Subarreglo más pequeño con suma mayor que un valor dado:

Dada una matriz llegar[] de números enteros y un número X , la tarea es encontrar el subconjunto más pequeño con una suma mayor que el valor dado.

Acercarse:

java núcleo java

Podemos solucionar este problema utilizando la técnica de ventana deslizante y manteniendo dos punteros: inicio y fin para marcar el inicio y el final de la ventana. Podemos seguir incrementando el puntero final hasta que la suma de la ventana sea menor o igual a X. Cuando la suma de la ventana sea mayor que X, registramos la longitud de la ventana y comenzamos a mover el puntero de inicio hasta la suma de la ventana. se vuelve menor o igual a X. Ahora, cuando la suma sea menor o igual a X, nuevamente comience a incrementar el puntero final. Continúe moviendo el puntero de inicio y fin hasta que lleguemos al final de la matriz.

3. Encuentre el subarreglo con la suma dada en un arreglo de números enteros no negativos:

Dada una matriz llegar[] de números enteros no negativos y un número entero suma , encuentre un subarreglo que se agregue a un dado suma .

Acercarse:

La idea es simple ya que sabemos que todos los elementos del subarreglo son positivos, por lo que si un subarreglo tiene una suma mayor que la suma dada entonces no hay posibilidad de que agregar elementos al subarreglo actual sea igual a la suma dada. Entonces la idea es utilizar un enfoque similar a un ventana deslizante .

• Comience con un subconjunto vacío.
• agregue elementos al subarreglo hasta que la suma sea menor que X (suma dada) .
• Si la suma es mayor que X , elimine elementos del comenzar del subarreglo actual.

4. Ventana más pequeña que contiene todos los caracteres de la propia cadena:

Acercarse:

Básicamente, una ventana de caracteres se mantiene mediante el uso de dos punteros, a saber comenzar y fin . Estos comenzar y fin Los punteros se pueden utilizar para reducir y aumentar el tamaño de la ventana respectivamente. Siempre que la ventana contiene todos los caracteres de una cadena dada, la ventana se reduce desde el lado izquierdo para eliminar caracteres adicionales y luego se compara su longitud con la ventana más pequeña encontrada hasta el momento.
Si en la ventana actual no se pueden eliminar más caracteres, entonces comenzamos a aumentar el tamaño de la ventana usando el fin hasta que todos los distintos caracteres presentes en la cadena también estén en la ventana. Finalmente, encuentre el tamaño mínimo de cada ventana.

Problemas de práctica sobre la técnica de la ventana corrediza:

Artículos relacionados:

• R Artículos recientes sobre la técnica de la ventana corrediza
• Preguntas de práctica sobre la ventana corrediza
• DSA a su propio ritmo: el curso más utilizado y confiable sobre DSA