Sliding Window-problemer er problemer der et fast eller variabelt vindu flyttes gjennom en datastruktur, vanligvis en matrise eller streng, for å løse problemer effektivt basert på kontinuerlige delsett av elementer. Denne teknikken brukes når vi trenger å finne undermatriser eller understrenger i henhold til et gitt sett med betingelser.

Skyvevindusteknikk

Innholdsfortegnelse

• Hva er skyvevindusteknikk?
• Hvordan bruke skyvevindusteknikk?
• Hvordan identifisere problemer med skyvevinduer
• Bruk tilfeller av skyvevindusteknikk
• Øv problemer på skyvevindusteknikk

Hva er skyvevindusteknikk?

Skyvevindusteknikk er en metode som brukes for å effektivt løse problemer som involverer å definere en vindu eller område i inngangsdataene (matriser eller strenger) og deretter flytte vinduet over dataene for å utføre en operasjon i vinduet. Denne teknikken brukes ofte i algoritmer som å finne undermatriser med en bestemt sum, finne den lengste understrengen med unike tegn, eller løse problemer som krever et vindu med fast størrelse for å behandle elementer effektivt.

La oss ta et eksempel for å forstå dette riktig, si at vi har en rekke størrelser N og også et heltall K. Nå må vi beregne den maksimale summen av en undergruppe som har størrelse nøyaktig K. Hvordan skal vi nå dette problemet?

En måte å gjøre dette på ved å ta hver undergruppe av størrelse K fra arrayen og finne ut den maksimale summen av disse undergruppene. Dette kan gjøres ved å bruke Nestede løkker som vil resultere i O(N²) Tidskompleksitet.

Men kan vi optimalisere denne tilnærmingen?

Svaret er Ja, i stedet for å ta hver K størrelse underarray og beregne summen, kan vi bare ta en K størrelse underarray fra 0 til K-1 indeks og beregne summen nå flytte vårt område en etter en sammen med iterasjonene og oppdatere resultatet, som i neste iterasjon øke til venstre og høyre peker og oppdater den forrige summen som vist i bildet nedenfor:

Skyvevindusteknikk

Følg nå denne metoden for hver iterasjon til vi når slutten av matrisen:

Skyvevindusteknikk

markdown-bilder

Så vi kan se at i stedet for å beregne summen av hver K-størrelse undergruppe, bruker vi forrige vindu med størrelse K, og ved å bruke resultatene oppdaterer vi summen og flytter vinduet til høyre ved å flytte pekere til venstre og høyre, denne operasjonen er optimal fordi den ta O(1) tid for å skifte området i stedet for å beregne på nytt.

Denne tilnærmingen med å flytte pekerne og beregne resultatene deretter er kjent som Skyvevindu Teknikk .

Hvordan bruke skyvevindusteknikk?

Det er i hovedsak to typer skyvevinduer:

1. Skyvevindu med fast størrelse:

De generelle trinnene for å løse disse spørsmålene ved å følge trinnene nedenfor:

• Finn størrelsen på vinduet som kreves, si K.
• Beregn resultatet for 1. vindu, dvs. inkluder de første K-elementene i datastrukturen.
• Bruk deretter en løkke til å skyve vinduet med 1 og fortsett å beregne resultatet vindu for vindu.

2. Skyvevindu med variabel størrelse:

De generelle trinnene for å løse disse spørsmålene ved å følge trinnene nedenfor:

• I denne typen skyvevindusproblemer øker vi høyre peker én etter én til tilstanden vår er sann.
• På ethvert trinn hvis tilstanden vår ikke samsvarer, krymper vi størrelsen på vinduet vårt ved å øke venstre peker.
• Igjen, når tilstanden vår er tilfredsstillende, begynner vi å øke den riktige pekeren og følger trinn 1.
• Vi følger disse trinnene til vi kommer til slutten av matrisen.

Slik identifiserer du problemer med skyvevinduer:

• Disse problemene krever generelt Finne Maksimum/Minimum Subarray , Understrenger som tilfredsstiller en bestemt betingelse.
• Størrelsen på undermatrisen eller understrengen ' K’ vil bli gitt i noen av problemene.
• Disse problemene kan enkelt løses i O(N²) tidskompleksitet ved bruk av nestede løkker, ved hjelp av skyvevindu kan vi løse disse i På) Tidskompleksitet.
• Nødvendig tidskompleksitet: O(N) eller O(Nlog(N))
• Begrensninger: N <= 10⁶, Hvis N er størrelsen på matrisen/strengen.

Bruk tilfeller av skyvevindusteknikk:

1. For å finne den maksimale summen av alle undermatriser av størrelse K:

Gitt en rekke heltall av størrelse 'n', Vårt mål er å beregne den maksimale summen av 'k' påfølgende elementer i matrisen.

Inndata: arr[] = {100, 200, 300, 400}, k = 2
Utgang: 700

Inndata: arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}, k = 4
Utgang: 39
Vi får maksimal sum ved å legge til undergruppe {4, 2, 10, 23} av størrelse 4.

Inndata: arr[] = {2, 3}, k = 3
Utgang: Ugyldig
Det er ingen undergruppe av størrelse 3, da størrelsen på hele matrisen er 2.

Naiv tilnærming: Så, la oss analysere problemet med Brute Force Approach . Vi starter med den første indeksen og summerer til kth element. Vi gjør det for alle mulige påfølgende blokker eller grupper av k elementer. Denne metoden krever en nestet for-løkke, den ytre for-løkken starter med startelementet til blokken av k-elementer, og den indre eller nestede løkken vil legge seg opp til det kth-elementet.

Nedenfor er implementeringen av tilnærmingen ovenfor:

// 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; } // Returnerer maksimal sum i en undergruppe av størrelsen k. int maxSum(int arr[], int n, int k) { // Initialiser resultat int max_sum = INT_MIN;  // Vurder alle blokker som starter med 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]);  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 ?>// O(n*k) løsning for å finne maksimal sum av // en undergruppe av størrelse k // Returnerer maksimal sum i en undergruppe av størrelse k. function maxSum($arr, $n, $k) { // Initialiser resultatet $max_sum = PHP_INT_MIN ; // Vurder alle blokker // som starter med i. for ( $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>

Tidskompleksitet: O(k*n) da den inneholder to nestede løkker.
Hjelpeplass: O(1)

Bruk skyvevindusteknikken:

• Vi beregner summen av de første k elementene ut av n ledd ved å bruke en lineær sløyfe og lagrer summen i variabel vindu_sum .
• Deretter vil vi krysse lineært over matrisen til den når slutten og samtidig holde styr på den maksimale summen.
• For å få den gjeldende summen av en blokk med k elementer, trekker du bare det første elementet fra den forrige blokken og legger til det siste elementet i den gjeldende blokken.

Representasjonen nedenfor vil gjøre det klart hvordan vinduet glir over matrisen.

Vurder en matrise arr[] = {5, 2, -1, 0, 3} og verdien av k = 3 og n = 5

Dette er den innledende fasen hvor vi har beregnet den innledende vindussummen fra indeks 0 . På dette stadiet er vindussummen 6. Nå setter vi maksimum_sum som gjeldende_vindu, dvs. 6.

Nå skyver vi vinduet vårt etter en enhetsindeks. Derfor kaster den nå 5 fra vinduet og legger til 0 til vinduet. Derfor vil vi få vår nye vindussum ved å trekke fra 5 og deretter legge til 0 til den. Så vindussummen vår blir nå 1. Nå vil vi sammenligne denne vindussummen med maksimum_sum. Siden den er mindre, endrer vi ikke maksimum_sum.

Tilsvarende, nå skyver vi igjen vinduet vårt med en enhetsindeks og får den nye vindussummen til å være 2. Igjen sjekker vi om denne gjeldende vindussummen er større enn maksimum_sum til nå. Nok en gang er den mindre, så vi endrer ikke maksimumsummen.
Derfor, for matrisen ovenfor er vår maksimumsum 6.

Nedenfor er koden for tilnærmingen ovenfor:

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

Tidskompleksitet: O(n), hvor n er størrelsen på inndatamatrisen arr[] .
Hjelpeplass: O(1)

2. Minste undergruppe med sum større enn en gitt verdi:

Gitt en matrise arr[] av heltall og et tall X , er oppgaven å finne den minste undergruppen med en sum som er større enn den gitte verdien.

Nærme seg:

Vi kan løse dette problemet ved å bruke Sliding Window Technique og opprettholde to pekere: start og slutt for å markere starten og slutten av vinduet. Vi kan fortsette å øke sluttpekeren til summen av vinduet er mindre enn eller lik X. Når summen av vinduet blir større enn X, registrerer vi lengden på vinduet og begynner å flytte startpekeren til summen av vinduet blir mindre enn eller lik X. Nå, når summen blir mindre enn eller lik X, start igjen å øke sluttpekeren. Fortsett å flytte start- og sluttpekeren til vi har nådd slutten av matrisen.

3. Finn undermatrise med gitt sum i en matrise med ikke-negative heltall:

Gitt en matrise arr[] av ikke-negative heltall og et heltall sum , finn en undergruppe som legger til en gitt sum .

Nærme seg:

Ideen er enkel ettersom vi vet at alle elementene i subarray er positive, så hvis en subarray har sum større enn gitt sum da er det ingen mulighet for at å legge til elementer til den gjeldende undergruppen vil være lik den gitte summen. Så ideen er å bruke en lignende tilnærming til en skyvevindu .

• Start med en tom undergruppe.
• legg til elementer i undermatrisen til summen er mindre enn x (gitt sum) .
• Hvis summen er større enn x , fjern elementer fra start av gjeldende undergruppe.

4. Det minste vinduet som inneholder alle tegnene i strengen:

Nærme seg:

hvordan lese en json-fil

I utgangspunktet opprettholdes et vindu med tegn ved å bruke to pekere, nemlig start og slutt . Disse start og slutt pekere kan brukes til å krympe og øke størrelsen på vinduet henholdsvis. Når vinduet inneholder alle tegn i gitt streng, krympes vinduet fra venstre side for å fjerne ekstra tegn, og deretter sammenlignes lengden med det minste vinduet som er funnet så langt.
Hvis det ikke kan slettes flere tegn i det nåværende vinduet, begynner vi å øke størrelsen på vinduet ved å bruke slutt til alle de distinkte tegnene i strengen også er der i vinduet. Til slutt finner du minimumsstørrelsen for hvert vindu.

Øv problemer på skyvevindusteknikk:

Relaterte artikler:

• R siste artikler om skyvevindusteknikk
• Øvingsspørsmål om skyvevindu
• DSA Self-Paced – Det mest brukte og pålitelige kurset på DSA