Els problemes de finestra lliscant són problemes en què una finestra de mida fixa o variable es mou a través d'una estructura de dades, normalment una matriu o una cadena, per resoldre problemes de manera eficient basant-se en subconjunts continus d'elements. Aquesta tècnica s'utilitza quan necessitem trobar subarrays o subcadenes segons un conjunt de condicions donat.

Tècnica de la finestra corredissa

Taula de contingut

• Què és la tècnica de la finestra corredissa?
• Com utilitzar la tècnica de la finestra corredissa?
• Com identificar problemes de finestres corredisses
• Casos d'ús de la tècnica de la finestra corredissa
• Pràctica de problemes sobre la tècnica de la finestra corredissa

Què és la tècnica de la finestra corredissa?

Tècnica de la finestra corredissa és un mètode utilitzat per resoldre de manera eficient problemes que impliquen definir a finestra o rang a les dades d'entrada (matrius o cadenes) i després movent aquesta finestra per les dades per realitzar alguna operació dins de la finestra. Aquesta tècnica s'utilitza habitualment en algorismes com trobar subbarrays amb una suma específica, trobar la subcadena més llarga amb caràcters únics o resoldre problemes que requereixen una finestra de mida fixa per processar elements de manera eficient.

Prenguem un exemple per entendre-ho correctament, diguem que tenim una sèrie de mides N i també un nombre enter K. Ara, hem de calcular exactament la suma màxima d'un subarray amb mida K. Ara com hem d'abordar aquest problema?

Una manera de fer-ho prenent cada subarray de mida K de la matriu i esbrina la suma màxima d'aquests subbarrays. Això es pot fer mitjançant bucles imbricats que donaran lloc a O(N²) Complexitat temporal.

Però podem optimitzar aquest enfocament?

La resposta és sí, en comptes de prendre cadascun K subbarray de mida i calculant la seva suma, només podem prendre una subbarra de mida K de l'índex 0 a K-1 i calcular la seva suma ara canviar el nostre rang un per un juntament amb les iteracions i actualitzar el resultat, com en la següent iteració augmentar l'esquerra i punter dret i actualitzeu la suma anterior tal com es mostra a la imatge següent:

Tècnica de la finestra corredissa

Ara seguiu aquest mètode per a cada iteració fins que arribem al final de la matriu:

Tècnica de la finestra corredissa

negreta en css

Així doncs, podem veure que en comptes de tornar a calcular la suma de cada subbarra de mida K estem utilitzant la finestra anterior de mida K i utilitzant els seus resultats actualitzem la suma i desplaçam la finestra cap a la dreta movent els punters esquerre i dret, aquesta operació és òptima perquè prengui O(1) temps per canviar l'interval en lloc de tornar a calcular.

Aquest enfocament de desplaçar els punters i calcular els resultats en conseqüència es coneix com Tècnica de la finestra corredissa .

Com utilitzar la tècnica de la finestra corredissa?

Bàsicament hi ha dos tipus de finestres corredisses:

1. Finestra corredissa de mida fixa:

Els passos generals per resoldre aquestes preguntes seguint els passos següents:

• Trobeu la mida de la finestra necessària, per exemple K.
• Calcula el resultat de la primera finestra, és a dir, inclou els primers K elements de l'estructura de dades.
• A continuació, utilitzeu un bucle per lliscar la finestra en 1 i seguiu calculant el resultat finestra per finestra.

2. Finestra corredissa de mida variable:

Els passos generals per resoldre aquestes preguntes seguint els passos següents:

• En aquest tipus de problema de finestres corredisses, augmentem el nostre punter dret un per un fins que la nostra condició sigui certa.
• En qualsevol pas si la nostra condició no coincideix, reduïm la mida de la nostra finestra augmentant el punter esquerre.
• De nou, quan la nostra condició es compleix, comencem a augmentar el punter correcte i seguim el pas 1.
• Seguim aquests passos fins arribar al final de la matriu.

Com identificar els problemes de la finestra corredissa:

• Aquests problemes generalment requereixen Trobar el màxim/mínim Subarray , Subcadenes que compleixen una condició específica.
• La mida de la subbarray o subcadena ' K' es donarà en alguns dels problemes.
• Aquests problemes es poden resoldre fàcilment en O(N²) complexitat temporal utilitzant bucles imbricats, mitjançant la finestra lliscant podem resoldre'ls O(n) Complexitat temporal.
• Complexitat temporal requerida: O(N) o O(Nlog(N))
• Restriccions: N <= 10⁶, Si N és la mida de la matriu/String.

Casos d'ús de la tècnica de la finestra corredissa:

1. Per trobar la suma màxima de tots els subarrays de mida K:

Donada una matriu de nombres enters de mida 'n', El nostre objectiu és calcular la suma màxima de 'k' elements consecutius de la matriu.

Entrada: arr[] = {100, 200, 300, 400}, k = 2
Sortida: 700

Entrada: arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}, k = 4
Sortida: 39
Obtenim la suma màxima afegint subbarray {4, 2, 10, 23} de la mida 4.

Entrada: arr[] = {2, 3}, k = 3
Sortida: Invàlid
No hi ha cap subarray de mida 3, ja que la mida de tota la matriu és 2.

Enfocament naïf: Per tant, analitzem el problema amb Aproximació a la força bruta . Comencem amb el primer índex i sumem fins al kth element. Ho fem per a tots els blocs o grups consecutius possibles de k elements. Aquest mètode requereix un bucle for imbricat, el bucle for exterior comença amb l'element inicial del bloc de k elements, i el bucle interior o imbricat s'acumularà fins a l'element k-è.

A continuació es mostra la implementació de l'enfocament 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>num2) ? num1: num2; } // Retorna la suma màxima en un subbarray de mida k. int maxSum(int arr[], int n, int k) { // Inicialitza el resultat int max_sum = INT_MIN;  // Considereu tots els blocs que comencen per i.  per (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ó O(n*k) per trobar la suma màxima de // una subbarra de mida k // Retorna la suma màxima en una subbarra de mida k. funció maxSum($arr, $n, $k) { // Inicialitzar el resultat $max_sum = PHP_INT_MIN ; // Considereu tots els blocs // començant per i. per ($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>

Complexitat temporal: O(k*n) ja que conté dos bucles imbricats.
Espai auxiliar: O(1)

Aplicant la tècnica de la finestra corredissa:

• Calculem la suma dels primers k elements a partir de n termes utilitzant un bucle lineal i emmagatzemem la suma en variable finestra_sum .
• A continuació, recorrerem linealment la matriu fins que arribi al final i simultàniament farem un seguiment de la suma màxima.
• Per obtenir la suma actual d'un bloc de k elements només cal restar el primer element del bloc anterior i afegir l'últim element del bloc actual.

La representació següent deixarà clar com es llisca la finestra sobre la matriu.

Considereu una matriu arr[] = {5, 2, -1, 0, 3} i valor de k = 3 i n = 5

Aquesta és la fase inicial on hem calculat la suma inicial de la finestra a partir de l'índex 0. En aquesta etapa, la suma de la finestra és 6. Ara, establim la suma màxima com a finestra_actual, és a dir, 6.

Ara, llisquem la nostra finestra per un índex d'unitat. Per tant, ara descarta 5 de la finestra i afegeix 0 a la finestra. Per tant, obtindrem la nostra nova suma de la finestra restant 5 i afegint-hi 0. Per tant, la nostra suma de finestres ara es converteix en 1. Ara, compararem aquesta suma de finestres amb la suma_màxima. Com que és més petit, no canviarem la suma màxima.

python o

De la mateixa manera, ara tornem a fer lliscar la nostra finestra per un índex d'unitat i obtenim que la suma de la nova finestra sigui 2. De nou comprovem si aquesta suma de la finestra actual és més gran que la suma_maxima fins ara. Una vegada més, és més petit, de manera que no canviem la suma màxima.
Per tant, per a la matriu anterior, la nostra màxima_sum és 6.

A continuació es mostra el codi de l'enfocament 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>

Complexitat temporal: O(n), on n és la mida de la matriu d'entrada arr[] .
Espai auxiliar: O(1)

2. La subbarra més petita amb una suma superior a un valor donat:

Donada una matriu arr[] de nombres enters i un nombre X , la tasca és trobar la subbarra més petita amb una suma més gran que el valor donat.

Enfocament:

Podem resoldre aquest problema utilitzant la tècnica de la finestra corredissa i mantenint dos punters: inici i final per marcar l'inici i el final de la finestra. Podem seguir augmentant el punter final fins que la suma de la finestra sigui menor o igual que X. Quan la suma de la finestra es fa més gran que X, registrem la longitud de la finestra i comencem a moure el punter inicial fins a la suma de la finestra. es fa més petit o igual que X. Ara, quan la suma sigui menor o igual que X, torneu a començar a incrementar el punter final. Continueu movent el punter inicial i final fins que hem arribat al final de la matriu.

3. Trobeu un subarray amb una suma donada en una matriu d'enters no negatius:

Donada una matriu arr[] de nombres enters no negatius i un nombre enter suma , trobeu un subbarray que s'afegeixi a un determinat suma .

Enfocament:

La idea és senzilla ja que sabem que tots els elements del subbarray són positius, per tant, si un subbarray té una suma més gran que la suma donada aleshores no hi ha possibilitat que sumar elements al subbarrat actual sigui igual a la suma donada. Per tant, la idea és utilitzar un enfocament similar a a finestra corredissa .

• Comenceu amb un subbarrat buit.
• afegir elements a la subbarra fins que la suma sigui menor que x (suma donada) .
• Si la suma és més gran que x , elimineu elements del començar del subarrai actual.

4. La finestra més petita que conté tots els caràcters de la pròpia cadena:

Enfocament:

Bàsicament es manté una finestra de caràcters utilitzant dos punters, és a dir començar i final . Aquests començar i final els punters es poden utilitzar per reduir i augmentar la mida de la finestra respectivament. Sempre que la finestra conté tots els caràcters de la cadena donada, la finestra es redueix des del costat esquerre per eliminar caràcters addicionals i després es compara la seva longitud amb la finestra més petita trobada fins ara.
Si a la finestra actual no es poden suprimir més caràcters, comencem a augmentar la mida de la finestra utilitzant el botó final fins que tots els caràcters diferents presents a la cadena també hi estiguin a la finestra. Finalment, cerqueu la mida mínima de cada finestra.

Problemes de pràctica sobre la tècnica de la finestra corredissa:

Articles relacionats:

• R Articles recents sobre la tècnica de la finestra corredissa
• Preguntes pràctiques sobre la finestra corredissa
• DSA Self-Paced: el curs més utilitzat i de confiança sobre DSA