Problémy s posuvným oknom sú problémy, pri ktorých sa okno s pevnou alebo premenlivou veľkosťou presúva cez dátovú štruktúru, zvyčajne pole alebo reťazec, aby sa problémy efektívne vyriešili na základe súvislých podmnožín prvkov. Táto technika sa používa, keď potrebujeme nájsť podpolia alebo podreťazce podľa daného súboru podmienok.

Technika posuvného okna

Obsah

• Čo je to technika posuvného okna?
• Ako používať techniku ​​posuvných okien?
• Ako identifikovať problémy s posuvnými oknami
• Prípady použitia techniky posuvných okien
• Cvičte problémy s technikou posuvných okien

Čo je to technika posuvného okna?

Technika posuvného okna je metóda používaná na efektívne riešenie problémov, ktoré zahŕňajú definovanie a okno alebo rozsah vo vstupných údajoch (poliach alebo reťazcoch) a potom presúvaním tohto okna cez údaje na vykonanie určitej operácie v rámci okna. Táto technika sa bežne používa v algoritmoch, ako je hľadanie podpolí s konkrétnym súčtom, hľadanie najdlhšieho podreťazca s jedinečnými znakmi alebo riešenie problémov, ktoré vyžadujú okno s pevnou veľkosťou na efektívne spracovanie prvkov.

Zoberme si príklad, aby sme to správne pochopili, povedzme, že máme pole veľkostí N a tiež celé číslo K. Teraz musíme vypočítať maximálny súčet podpola, ktorý má presne veľkosť K. Ako by sme teraz mali pristupovať k tomuto problému?

Jedným zo spôsobov, ako to urobiť, je vziať každé podpole veľkosti K z poľa a zistiť maximálny súčet týchto podpolí. Dá sa to urobiť pomocou vnorených slučiek, ktorých výsledkom bude O(N²) Časová zložitosť.

Môžeme však tento prístup optimalizovať?

Odpoveď je áno, namiesto toho, aby ste brali každý K s veľkosťou podpolia a vypočítaním jeho súčtu, môžeme jednoducho vziať jedno podpole veľkosti K od 0 do indexu K-1 a vypočítať jeho súčet teraz posunúť náš rozsah jeden po druhom spolu s iteráciami a aktualizovať výsledok, ako v ďalšej iterácii zvýšiť vľavo a pravý ukazovateľ a aktualizujte predchádzajúci súčet, ako je znázornené na obrázku nižšie:

Technika posuvného okna

Teraz postupujte podľa tejto metódy pre každú iteráciu, kým sa nedostaneme na koniec poľa:

Technika posuvného okna

stiahnite si videá z youtube pomocou vlc

Môžeme teda vidieť, že namiesto prepočítavania súčtu každého podpola veľkosti K používame predchádzajúce okno veľkosti K a pomocou jeho výsledkov aktualizujeme súčet a posúvame okno doprava pohybom ľavého a pravého ukazovateľa, táto operácia je optimálna, pretože trvať O(1) čas na posunutie rozsahu namiesto prepočítavania.

Tento prístup posúvania ukazovateľov a zodpovedajúcich výpočtov výsledkov je známy ako Technika posuvného okna .

Ako používať techniku ​​posuvných okien?

V zásade existujú dva typy posuvných okien:

1. Posuvné okno s pevnou veľkosťou:

Všeobecné kroky na vyriešenie týchto otázok podľa nasledujúcich krokov:

• Nájdite požadovanú veľkosť okna, povedzme K.
• Vypočítajte výsledok pre 1. okno, t.j. zahrňte prvých K prvkov dátovej štruktúry.
• Potom pomocou slučky posúvajte okno o 1 a pokračujte vo výpočte výsledku okno po okne.

2. Posuvné okno s premenlivou veľkosťou:

Všeobecné kroky na vyriešenie týchto otázok podľa nasledujúcich krokov:

• Pri tomto type problému s posuvným oknom zvyšujeme náš pravý ukazovateľ jeden po druhom, kým sa naša podmienka nestane pravdivou.
• V každom kroku, ak sa naša podmienka nezhoduje, zmenšíme veľkosť nášho okna zvýšením ľavého ukazovateľa.
• Opäť, keď náš stav uspokojí, začneme zvyšovať správny ukazovateľ a postupujte podľa kroku 1.
• Postupujte podľa týchto krokov, kým sa nedostaneme na koniec poľa.

Ako identifikovať problémy s posuvným oknom:

• Tieto problémy vo všeobecnosti vyžadujú nájsť maximum/minimum Subarray , Podreťazce ktoré spĺňajú určitú podmienku.
• Veľkosť podpola alebo podreťazca „ K' bude daný v niektorých problémoch.
• Tieto problémy možno ľahko vyriešiť v O(N²) časová zložitosť pomocou vnorených slučiek, pomocou posuvného okna ich vieme vyriešiť v O(n) Časová zložitosť.
• Požadovaná časová náročnosť: O(N) alebo O(Nlog(N))
• Obmedzenia: N <= 10⁶, Ak N je veľkosť poľa/reťazca.

Prípady použitia techniky posuvných okien:

1. Ak chcete nájsť maximálny súčet všetkých podpolí veľkosti K:

Dané pole celých čísel veľkosti ‚n‘, Naším cieľom je vypočítať maximálny súčet „k“ po sebe idúce prvky v poli.

Vstup: arr[] = {100, 200, 300, 400}, k = 2
Výkon : 700

Vstup: arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}, k = 4
Výkon : 39
Maximálny súčet získame pridaním podpola {4, 2, 10, 23} veľkosti 4.

Vstup: arr[] = {2, 3}, k = 3
Výkon : Neplatné
Neexistuje žiadne podpole veľkosti 3, pretože veľkosť celého poľa je 2.

Naivný prístup: Poďme teda analyzovať problém s Prístup hrubou silou . Začneme prvým indexom a súčtom do kth element. Robíme to pre všetky možné po sebe idúce bloky alebo skupiny k prvkov. Táto metóda vyžaduje vnorenú slučku for, vonkajšia slučka for začína počiatočným prvkom bloku k prvkov a vnútorná alebo vnorená slučka sa bude sčítavať až po k-tý prvok.

Nižšie je uvedená implementácia vyššie uvedeného prístupu:

pole v jazyku Java

// 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>číslo 2) ? číslo1: číslo2; } // Vráti maximálny súčet v podpole s veľkosťou k. int maxSum(int arr[], int n, int k) { // Inicializácia výsledku int max_sum = INT_MIN;  // Zvážte všetky bloky začínajúce na i.  pre (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) riešenie na nájdenie maximálneho súčtu // podpole veľkosti k // Vráti maximálny súčet v podpoli s veľkosťou k. function maxSum($arr, $n, $k) { // Inicializácia výsledku $max_sum = PHP_INT_MIN ; // Zvážte všetky bloky // počnúc i. pre ( $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>

Časová zložitosť: O(k*n), pretože obsahuje dve vnorené slučky.
Pomocný priestor: O(1)

Použitie techniky posuvných okien:

• Vypočítame súčet prvých k prvkov z n členov pomocou lineárnej slučky a uložíme súčet do premennej window_sum .
• Potom budeme lineárne prechádzať po poli, kým nedosiahne koniec a súčasne sledovať maximálny súčet.
• Ak chcete získať aktuálny súčet bloku k prvkov, stačí odpočítať prvý prvok od predchádzajúceho bloku a pridať posledný prvok aktuálneho bloku.

Z nižšie uvedeného znázornenia bude jasné, ako sa okno posúva po poli.

Zvážte pole arr[] = {5, 2, -1, 0, 3} a hodnota k = 3 a n = 5

Toto je počiatočná fáza, v ktorej sme vypočítali počiatočný súčet okna od indexu 0. V tejto fáze je súčet okna 6. Teraz nastavíme maximálny_sum ako aktuálne_okno, tj 6.

Teraz posúvame naše okno o index jednotky. Preto teraz zahodí 5 z okna a pridá 0 do okna. Náš nový súčet okna teda dostaneme odpočítaním 5 a následným pripočítaním 0 k nemu. Takže náš súčet okien sa teraz stane 1. Teraz porovnáme tento súčet okien s maximálnym_sumom. Keďže je menší, maximálny_sum nezmeníme.

Podobne teraz opäť posunieme naše okno o index jednotky a získame súčet nového okna na 2. Opäť skontrolujeme, či je tento súčet aktuálneho okna väčší ako doteraz maximálny_súčet. Opäť je to menšie, takže maximálny_sum nemeníme.
Preto pre vyššie uvedené pole je náš maximálny_sum 6.

Nižšie je uvedený kód pre vyššie uvedený prístup:

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

Časová zložitosť: O(n), kde n je veľkosť vstupného poľa arr[] .
Pomocný priestor: O(1)

2. Najmenšie podpole so súčtom väčším ako daná hodnota:

Dané pole arr[] celých čísel a čísla X , úlohou je nájsť najmenšie podpole so súčtom väčším ako je zadaná hodnota.

Prístup:

Tento problém môžeme vyriešiť pomocou techniky posuvného okna a zachovaním dvoch ukazovateľov: začiatok a koniec na označenie začiatku a konca okna. Môžeme neustále zvyšovať koncový ukazovateľ, až kým súčet okna nebude menší alebo rovný X. Keď sa súčet okna stane väčším ako X, zaznamenáme dĺžku okna a začneme posúvať počiatočný ukazovateľ na súčet okna sa stane menším alebo rovným X. Teraz, keď bude súčet menší alebo rovný X, začnite opäť zvyšovať koncový ukazovateľ. Pokračujte v posúvaní počiatočného a koncového ukazovateľa, kým nedosiahneme koniec poľa.

3. Nájdite podpole s daným súčtom v poli nezáporných celých čísel:

Dané pole arr[] nezáporných celých čísel a celého čísla súčet , nájdite podpole, ktoré pridáva k danej súčet .

Prístup:

Myšlienka je jednoduchá, pretože vieme, že všetky prvky v podpole sú kladné, takže ak má podpole súčet väčší ako daná suma potom neexistuje možnosť, že pridanie prvkov do aktuálneho podpola sa bude rovnať danému súčtu. Myšlienkou je teda použiť podobný prístup ako a posuvné okno .

• Začnite s prázdnou podpolou.
• pridávajte prvky do podpola, kým súčet nebude menší ako X (daná suma) .
• Ak je súčet väčší ako X , odstráňte prvky z začať aktuálneho podpola.

4. Najmenšie okno, ktoré obsahuje všetky znaky samotného reťazca:

Prístup:

V zásade sa okno znakov udržiava pomocou dvoch ukazovateľov začať a koniec . Títo začať a koniec Ukazovatele možno použiť na zmenšenie a zväčšenie veľkosti okna. Vždy, keď okno obsahuje všetky znaky daného reťazca, okno sa z ľavej strany zmenší, aby sa odstránili nadbytočné znaky a potom sa jeho dĺžka porovná s najmenším doteraz nájdeným oknom.
Ak v tomto okne nie je možné odstrániť žiadne ďalšie znaky, potom začneme zväčšovať veľkosť okna pomocou koniec kým všetky odlišné znaky prítomné v reťazci nebudú aj v okne. Nakoniec nájdite minimálnu veľkosť každého okna.

Cvičné problémy techniky posuvných okien:

Súvisiace články:

• R najnovšie články o technike posuvných okien
• Cvičné otázky o posuvnom okne
• DSA vlastným tempom – najpoužívanejší a najdôveryhodnejší kurz o DSA