logo

TechCodeview

Technika posuvného okna

Problémy s posuvnými okny jsou problémy, při kterých se okno s pevnou nebo proměnnou velikostí přesouvá přes datovou strukturu, obvykle pole nebo řetězec, za účelem efektivního řešení problémů na základě spojitých podmnožin prvků. Tato technika se používá, když potřebujeme najít podpole nebo podřetězce podle dané sady podmínek.

Technika posuvného okna



Obsah

Co je technika posuvného okna?

Technika posuvného okna je metoda používaná k efektivnímu řešení problémů, které zahrnují definování a okno nebo rozsah ve vstupních datech (pole nebo řetězce) a poté přesouváním tohoto okna přes data pro provedení nějaké operace v okně. Tato technika se běžně používá v algoritmech, jako je hledání podpolí se specifickým součtem, hledání nejdelšího podřetězce s jedinečnými znaky nebo řešení problémů, které vyžadují okno s pevnou velikostí pro efektivní zpracování prvků.

Vezměme si příklad, abychom to správně pochopili, řekněme, že máme pole velikostí N a také celé číslo K. Nyní musíme vypočítat maximální součet podpole, která má přesně velikost K. Jak bychom nyní měli k tomuto problému přistupovat?



Jedním ze způsobů, jak toho dosáhnout, je vzít každé podpole o velikosti K z pole a zjistit maximální součet těchto podpolí. To lze provést pomocí vnořených smyček, které povedou k O(N2) Časová složitost.

Můžeme však tento přístup optimalizovat?

Odpověď zní Ano, místo toho, abyste brali každý K velikosti podpole a výpočtu jeho součtu, stačí vzít jedno podpole velikosti K od 0 do indexu K-1 a vypočítat jeho součet, nyní posouváme náš rozsah jeden po druhém spolu s iteracemi a aktualizujeme výsledek, jako v další iteraci zvětšíme doleva a pravý ukazatel a aktualizujte předchozí součet, jak je znázorněno na obrázku níže:



Technika posuvného okna

Nyní postupujte podle této metody pro každou iteraci, dokud nedosáhneme konce pole:

Technika posuvného okna

herec saira banu

Můžeme tedy vidět, že místo přepočítávání součtu každého podpole o velikosti K používáme předchozí okno velikosti K a pomocí jeho výsledků aktualizujeme součet a posouváme okno doprava pohybem levého a pravého ukazatele, tato operace je optimální, protože trvat O(1) čas k posunutí rozsahu místo přepočítávání.

Tento přístup posouvání ukazatelů a odpovídající výpočet výsledků je známý jako Technika posuvného okna .

Jak používat techniku ​​posuvných oken?

V zásadě existují dva typy posuvných oken:

1. Posuvné okno s pevnou velikostí:

Obecné kroky k vyřešení těchto otázek pomocí následujících kroků:

  • Najděte požadovanou velikost okna, řekněte K.
  • Vypočítejte výsledek pro 1. okno, tj. zahrňte prvních K prvků datové struktury.
  • Poté pomocí smyčky posuňte okno o 1 a pokračujte ve výpočtu výsledku okno po okně.

2. Posuvné okno s proměnnou velikostí:

Obecné kroky k vyřešení těchto otázek pomocí následujících kroků:

  • V tomto typu problému s posuvným oknem zvyšujeme náš pravý ukazatel jeden po druhém, dokud naše podmínka není pravdivá.
  • V každém kroku, pokud se naše podmínka neshoduje, zmenšujeme velikost našeho okna zvýšením levého ukazatele.
  • Opět, když naše kondice vyhovuje, začneme zvyšovat správný ukazatel a následujeme krok 1.
  • Takto postupujeme, dokud se nedostaneme na konec pole.

Jak identifikovat problémy s posuvným oknem:

  • Tyto problémy obecně vyžadují nalezení maxima/minima Subarray , Podřetězce které splňují nějakou konkrétní podmínku.
  • Velikost podpole nebo podřetězce „ K' budou uvedeny v některých problémech.
  • Tyto problémy lze snadno vyřešit v O(N2) časovou složitost pomocí vnořených smyček, pomocí posuvného okna je můžeme vyřešit Na) Časová složitost.
  • Požadovaná časová náročnost: O(N) nebo O(Nlog(N))
  • Omezení: N <= 106, Pokud N je velikost pole/řetězce.

Příklady použití techniky posuvných oken:

1. Chcete-li najít maximální součet všech dílčích polí velikosti K:

Dané pole celých čísel velikosti ‚n‘, Naším cílem je vypočítat maximální součet 'k' po sobě jdoucích prvků v poli.

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

Vstup : arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}, k = 4
Výstup : 39
Maximální součet získáme přidáním podpole {4, 2, 10, 23} velikosti 4.

Vstup : arr[] = {2, 3}, k = 3
Výstup : Neplatný
Neexistuje žádné podpole o velikosti 3, protože velikost celého pole je 2.

Naivní přístup: Pojďme tedy analyzovat problém s Přístup hrubou silou . Začneme prvním indexem a součtem do kth živel. Děláme to pro všechny možné po sobě jdoucí bloky nebo skupiny k prvků. Tato metoda vyžaduje vnořenou smyčku for, vnější smyčka for začíná počátečním prvkem bloku k prvků a vnitřní nebo vnořená smyčka bude sčítat až k-tý prvek.

Níže je uvedena implementace výše uvedeného přístupu:

C++ 
// 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)>
C 
// 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átí maximální součet v dílčím poli o velikosti k. int maxSum(int arr[], int n, int k) { // Inicializace výsledku int max_sum = INT_MIN;  // Zvažte všechny bloky začínající na 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)>
Jáva 
// 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)>
Python3 
# 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# 
// 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.>
JavaScript 
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));>
PHP 
 // code ?>// O(n*k) řešení pro nalezení maximálního součtu // podpole o velikosti k // Vrací maximální součet v podpoli o velikosti k. function maxSum($arr, $n, $k) { // Inicializace výsledku $max_sum = PHP_INT_MIN ; // Zvažte všechny bloky // počínaje i. pro ( $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. ?>>
Výstup 
24>

Časová složitost: O(k*n), protože obsahuje dvě vnořené smyčky.
Pomocný prostor: O(1)

Použití techniky posuvných oken:

  • Vypočítáme součet prvních k prvků z n členů pomocí lineární smyčky a uložíme součet do proměnné okno_součet .
  • Poté se budeme lineárně pohybovat po poli, dokud nedosáhne konce a současně sledovat maximální součet.
  • Chcete-li získat aktuální součet bloku k prvků, stačí odečíst první prvek od předchozího bloku a přidat poslední prvek aktuálního bloku.

Níže uvedená reprezentace jasně ukáže, jak se okno posouvá přes pole.

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

Toto je počáteční fáze, kdy jsme vypočítali počáteční součet okna počínaje indexem 0. V této fázi je součet okna 6. Nyní nastavíme maximální_součet jako aktuální_okno, tj. 6.

Nyní posuneme naše okno o index jednotek. Proto nyní zahodí 5 z okna a přidá 0 do okna. Náš nový součet okna tedy získáme odečtením 5 a následným přičtením 0 k němu. Takže náš součet okna je nyní 1. Nyní porovnáme tento součet okna s maximálním_součtem. Protože je menší, nebudeme měnit maximální_součet.

nahradit řetězec java


Podobně nyní znovu posuneme naše okno o index jednotky a získáme součet nového okna na hodnotu 2. Znovu zkontrolujeme, zda je tento součet aktuálního okna větší než dosud maximální_součet. Opět je menší, takže maximální_součet neměníme.
Proto pro výše uvedené pole je náš maximální_sum 6.

Níže je uveden kód pro výše uvedený přístup:

C++ 
// 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; }>
Jáva 
// 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.>
Python3 
# 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# 
// 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.>
JavaScript 
>
PHP 
 // 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 ?>>
Výstup 
24>

Časová náročnost: O(n), kde n je velikost vstupního pole arr[] .
Pomocný prostor: O(1)

2. Nejmenší podpole se součtem větším než daná hodnota:

Dané pole arr[] celých čísel a čísla X , úkolem je najít nejmenší podpole se součtem větším, než je zadaná hodnota.

Přístup:

Tento problém můžeme vyřešit pomocí techniky posuvného okna a zachováním dvou ukazatelů: začátek a konec pro označení začátku a konce okna. Koncový ukazatel můžeme neustále zvyšovat, dokud součet okna nebude menší nebo roven X. Když se součet okna zvětší než X, zaznamenáme délku okna a začneme posouvat počáteční ukazatel na součet okna se stane menším nebo rovným X. Nyní, když se součet stane menším nebo rovným X, začněte znovu zvyšovat koncový ukazatel. Pokračujte v pohybu počátečního a koncového ukazatele, dokud nedosáhneme konce pole.

3. Najděte podpole s daným součtem v poli nezáporných celých čísel:

Dané pole arr[] nezáporných celých čísel a celého čísla součet , najděte podpole, která přidává k danému součet .

Přístup:

Myšlenka je jednoduchá, protože víme, že všechny prvky v dílčím poli jsou kladné, takže pokud má dílčí pole součet větší než daná suma pak neexistuje možnost, že přidání prvků do aktuálního podpole se bude rovnat danému součtu. Myšlenka je tedy použít podobný přístup jako a Posuvné okno .

  • Začněte s prázdnou podpolí.
  • přidávejte prvky do podpole, dokud nebude součet menší než X (daný součet) .
  • Pokud je součet větší než X , odstraňte prvky z Start aktuálního podpole.

4. Nejmenší okno, které obsahuje všechny znaky samotného řetězce:

Přístup:

V zásadě je okno znaků udržováno pomocí dvou ukazatelů Start a konec . Tyto Start a konec ukazatele lze použít ke zmenšení a zvětšení velikosti okna. Kdykoli okno obsahuje všechny znaky daného řetězce, okno se z levé strany zmenší, aby se odstranily přebytečné znaky, a poté se jeho délka porovná s nejmenším dosud nalezeným oknem.
Pokud v tomto okně nelze smazat žádné další znaky, začneme zvětšovat velikost okna pomocí konec dokud všechny odlišné znaky přítomné v řetězci nebudou také v okně. Nakonec najděte minimální velikost každého okna.

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

Problém

Odkaz na problém

Najděte Subarray s daným součtem

Řešit

Maximum posuvného okna (Maximum všech dílčích polí velikosti K)

Řešit

Nejdelší dílčí pole se součtem K

Řešit

Najděte maximální (nebo minimální) součet podpole o velikosti k

Řešit

Nejmenší okno v řetězci obsahující všechny znaky jiného řetězce

Řešit

Délka nejdelšího podřetězce bez opakujících se znaků

Řešit

První záporné celé číslo v každém okně o velikosti k

int to char java

Řešit

Počítejte odlišné prvky v každém okně velikosti k

Řešit

Nejmenší okno, které obsahuje všechny znaky samotného řetězce

Řešit

Podpole s největším součtem s alespoň k čísly

Řešit

Související články:

  • R poslední články o technice posuvných oken
  • Cvičné otázky o posuvném okně
  • DSA Self-Paced – nejpoužívanější a nejdůvěryhodnější kurz DSA