Problemy z przesuwanym oknem to problemy, w których okno o stałym lub zmiennym rozmiarze jest przesuwane przez strukturę danych, zazwyczaj tablicę lub ciąg znaków, w celu wydajnego rozwiązywania problemów w oparciu o ciągłe podzbiory elementów. Technikę tę stosuje się, gdy musimy znaleźć podtablice lub podciągi zgodnie z danym zestawem warunków.

Technika przesuwanego okna

Spis treści

• Na czym polega technika przesuwanego okna?
• Jak zastosować technikę przesuwanego okna?
• Jak rozpoznać problemy z przesuwanymi oknami
• Przypadki użycia techniki przesuwanego okna
• Ćwicz problemy dotyczące techniki przesuwanego okna

Na czym polega technika przesuwanego okna?

Technika przesuwanego okna to metoda stosowana do skutecznego rozwiązywania problemów wymagających zdefiniowania a okno Lub zakres w danych wejściowych (tablice lub ciągi znaków), a następnie przesuwając to okno po danych, aby wykonać jakąś operację w oknie. Technika ta jest powszechnie stosowana w algorytmach, takich jak znajdowanie podtablic o określonej sumie, znajdowanie najdłuższego podciągu z unikalnymi znakami lub rozwiązywanie problemów wymagających okna o stałym rozmiarze do wydajnego przetwarzania elementów.

Aby to właściwie zrozumieć, weźmy przykład, powiedzmy, że mamy tablicę rozmiarów N a także liczba całkowita K. Teraz musimy obliczyć maksymalną sumę podtablicy o dokładnym rozmiarze K. Jak teraz podejść do tego problemu?

Jednym ze sposobów osiągnięcia tego jest pobranie z tablicy każdej podtablicy o rozmiarze K i znalezienie maksymalnej sumy tych podtablic. Można to zrobić za pomocą pętli zagnieżdżonych, których wynikiem będzie O(N²) Złożoność czasowa.

Ale czy możemy zoptymalizować to podejście?

Odpowiedź brzmi: Tak, zamiast brać każde z nich K wielkości podtablicy i obliczając jej sumę, możemy po prostu wziąć jedną podtablicę rozmiaru K od 0 do indeksu K-1 i obliczyć jej sumę, teraz przesuwaj nasz zakres jeden po drugim wraz z iteracjami i aktualizuj wynik, tak jak w następnej iteracji zwiększ lewą i prawy wskaźnik i zaktualizuj poprzednią sumę, jak pokazano na poniższym obrazku:

Technika przesuwanego okna

Teraz postępuj zgodnie z tą metodą dla każdej iteracji, aż dotrzemy do końca tablicy:

Technika przesuwanego okna

Linux edytuj plik

Widzimy więc, że zamiast przeliczać sumę każdej podtablicy o rozmiarze K, używamy poprzedniego okna o rozmiarze K i wykorzystując jego wyniki aktualizujemy sumę i przesuwamy okno w prawo przesuwając wskaźniki w lewo i w prawo, operacja ta jest optymalna, ponieważ poświęć czas O(1), aby przesunąć zakres, zamiast przeliczać.

Takie podejście polegające na przesuwaniu wskaźników i odpowiednim obliczaniu wyników jest znane jako Technika przesuwanego okna .

Jak zastosować technikę przesuwanego okna?

Zasadniczo istnieją dwa rodzaje okien przesuwnych:

1. Okno przesuwne o stałym rozmiarze:

Ogólne kroki, aby rozwiązać te pytania, wykonując poniższe kroki:

• Znajdź wymagany rozmiar okna, powiedz K.
• Oblicz wynik dla pierwszego okna, czyli uwzględnij pierwszych K elementów struktury danych.
• Następnie użyj pętli, aby przesunąć okno o 1 i kontynuuj obliczanie wyniku okno po oknie.

2. Okno przesuwne o zmiennym rozmiarze:

Ogólne kroki, aby rozwiązać te pytania, wykonując poniższe kroki:

• W tego typu problemie z przesuwanym oknem zwiększamy prawy wskaźnik jeden po drugim, aż nasz warunek będzie prawdziwy.
• Na każdym kroku, jeśli nasz warunek nie pasuje, zmniejszamy rozmiar naszego okna, zwiększając lewy wskaźnik.
• Ponownie, gdy nasz warunek jest spełniony, zaczynamy zwiększać prawy wskaźnik i wykonujemy krok 1.
• Wykonujemy te kroki, aż dotrzemy do końca tablicy.

Jak rozpoznać problemy z przesuwanymi oknami:

• Problemy te zazwyczaj wymagają znalezienia maksimum/minimumu Podtablica , Podciągi które spełniają jakiś konkretny warunek.
• Rozmiar podtablicy lub podciągu „ K’ zostaną podane w niektórych problemach.
• Problemy te można łatwo rozwiązać w O(N²) złożoność czasową przy użyciu zagnieżdżonych pętli, przy użyciu przesuwanego okna możemy je rozwiązać NA) Złożoność czasu.
• Wymagana złożoność czasowa: O(N) lub O(Nlog(N))
• Ograniczenia: N <= 10⁶, Jeśli N jest rozmiarem tablicy/łańcucha.

Przypadki użycia techniki przesuwanego okna:

1. Aby znaleźć maksymalną sumę wszystkich podtablic o rozmiarze K:

Biorąc pod uwagę tablicę liczb całkowitych o rozmiarze 'N', Naszym celem jest obliczenie maksymalnej sumy „k” kolejne elementy tablicy.

Wejście : tablica [] = {100, 200, 300, 400}, k = 2
Wyjście : 700

Wejście : tablica [] = {1, 4, 2, 10, 23, 3, 1, 0, 20}, k = 4
Wyjście : 39
Maksymalną sumę otrzymujemy dodając podtablicę {4, 2, 10, 23} o rozmiarze 4.

Wejście : arr[] = {2, 3}, k = 3
Wyjście : Nieważny
Nie ma podtablicy o rozmiarze 3, ponieważ rozmiar całej tablicy wynosi 2.

Naiwne podejście: Przeanalizujmy więc problem z Podejście brutalnej siły . Zaczynamy od pierwszego indeksu i sumujemy do kth element. Robimy to dla wszystkich możliwych kolejnych bloków lub grup k elementów. Ta metoda wymaga zagnieżdżonej pętli for, zewnętrzna pętla zaczyna się od elementu początkowego bloku k elementów, a wewnętrzna lub zagnieżdżona pętla będzie sumować się aż do k-tego elementu.

Poniżej implementacja powyższego podejścia:

// 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>liczba2)? liczba1: liczba2; } // Zwraca maksymalną sumę w podtablicy o rozmiarze k. int maxSum(int arr[], int n, int k) { // Zainicjuj wynik int max_sum = INT_MIN;  // Rozważ wszystkie bloki zaczynające się od i.  for (int i = 0; tj< 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) rozwiązanie do znalezienia maksymalnej sumy // podtablicy o rozmiarze k // Zwraca maksymalną sumę w podtablicy o rozmiarze k. funkcja maxSum($arr, $n, $k) { // Zainicjuj wynik $max_sum = PHP_INT_MIN; // Weź pod uwagę wszystkie bloki // zaczynając od i. dla ( $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>

Złożoność czasowa: O(k*n), ponieważ zawiera dwie zagnieżdżone pętle.
Przestrzeń pomocnicza: O(1)

Zastosowanie techniki okna przesuwnego:

• Obliczamy sumę pierwszych k elementów z n składników za pomocą pętli liniowej i przechowujemy sumę w zmiennej suma_okna .
• Następnie będziemy przemieszczać się liniowo po tablicy, aż dotrze do końca, jednocześnie śledząc maksymalną sumę.
• Aby otrzymać aktualną sumę bloku k elementów, wystarczy odjąć pierwszy element od poprzedniego bloku i dodać ostatni element bieżącego bloku.

Poniższa reprezentacja wyjaśni, w jaki sposób okno przesuwa się po tablicy.

Rozważ tablicę arr[] = {5, 2, -1, 0, 3} i wartość k = 3 i N = 5

Jest to początkowa faza, w której obliczyliśmy początkową sumę okna, zaczynając od indeksu 0. Na tym etapie suma okna wynosi 6. Teraz ustawiamy maksymalną sumę jako bieżące_okno, tj. 6.

Teraz przesuwamy nasze okno o indeks jednostek. Dlatego teraz odrzuca 5 z okna i dodaje 0 do okna. W związku z tym otrzymamy nową sumę okna, odejmując 5, a następnie dodając do niej 0. Zatem suma naszego okna wynosi teraz 1. Teraz porównamy tę sumę okna z sumą maksymalną. Ponieważ jest mniejsza, nie zmienimy maksymalnej_sumy.

Podobnie, teraz ponownie przesuwamy nasze okno o indeks jednostki i otrzymujemy nową sumę okna wynoszącą 2. Ponownie sprawdzamy, czy bieżąca suma okna jest większa niż dotychczasowa maksymalna_suma. Po raz kolejny jest mniejszy, więc nie zmieniamy maksymalnej_sumy.
Dlatego dla powyższej tablicy nasza maksymalna suma wynosi 6.

Poniżej znajduje się kod powyższego podejścia:

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

Złożoność czasowa: O(n), gdzie N to rozmiar tablicy wejściowej arr[] .
Przestrzeń pomocnicza: O(1)

2. Najmniejsza podtablica z sumą większą od podanej wartości:

Biorąc pod uwagę tablicę arr[] liczb całkowitych i liczb X , zadaniem jest znalezienie najmniejszej podtablicy o sumie większej niż podana wartość.

Zbliżać się:

Możemy rozwiązać ten problem, stosując technikę przesuwanego okna i utrzymując dwa wskaźniki: początek i koniec, aby zaznaczyć początek i koniec okna. Możemy zwiększać wskaźnik końcowy, aż suma okna będzie mniejsza lub równa X. Kiedy suma okien stanie się większa niż X, rejestrujemy długość okna i zaczynamy przesuwać wskaźnik początkowy aż do sumy okien staje się mniejszy lub równy X. Teraz, gdy suma staje się mniejsza lub równa X, ponownie zacznij zwiększać wskaźnik końcowy. Kontynuuj przesuwanie wskaźników początku i końca, aż dotrzemy do końca tablicy.

3. Znajdź podtablicę o podanej sumie w tablicy nieujemnych liczb całkowitych:

Biorąc pod uwagę tablicę arr[] nieujemnych liczb całkowitych i liczby całkowitej suma , znajdź podtablicę, która dodaje do danego suma .

Zbliżać się:

czy Kat Timf jest prawnikiem

Pomysł jest prosty, ponieważ wiemy, że wszystkie elementy podtablicy są dodatnie, więc jeśli podtablica ma sumę większą niż podana suma wówczas nie ma możliwości, aby dodanie elementów do aktualnej podtablicy było równe podanej sumie. Pomysł polega więc na zastosowaniu podobnego podejścia do a okno przesuwne .

• Zacznij od pustej podtablicy.
• dodawaj elementy do podtablicy, aż suma będzie mniejsza niż X (podana suma) .
• Jeśli suma jest większa niż X , usuń elementy z początek bieżącej podtablicy.

4. Najmniejsze okno zawierające wszystkie znaki samego łańcucha:

Zbliżać się:

Zasadniczo okno znaków jest utrzymywane za pomocą dwóch wskaźników, a mianowicie początek I koniec . Te początek I koniec wskaźników można używać odpowiednio do zmniejszania i zwiększania rozmiaru okna. Ilekroć okno zawiera wszystkie znaki danego ciągu, okno jest zmniejszane od lewej strony w celu usunięcia dodatkowych znaków, a następnie jego długość jest porównywana z najmniejszym dotychczas znalezionym oknem.
Jeśli w obecnym oknie nie można usunąć już żadnych znaków to zaczynamy zwiększać rozmiar okna za pomocą koniec dopóki wszystkie odrębne znaki obecne w ciągu nie znajdą się również w oknie. Na koniec znajdź minimalny rozmiar każdego okna.

Ćwicz problemy dotyczące techniki przesuwanego okna:

Powiązane artykuły:

• R Ostatnie artykuły na temat techniki okien przesuwnych
• Ćwicz pytania dotyczące przesuwanego okna
• DSA Self-Paced — najczęściej używany i zaufany kurs DSA