Sliding window nümunəsi

codex

Sliding window nümunəsi bir “pəncərə” yaratmaqdan ibarətdir. Bu “pəncərə” ya bir massivdəki elementlər qrupu, ya da bir rəqəm ola bilər. Müəyyən şərtlərə əsasən “pəncərə” genişlənə və ya bağlana bilər (və ya yeni bir “pəncərə” yaradıla bilər).

Bu nümunə, massivdə və ya sətirdə məlumat alt dəstini izləmək üçün çox faydalıdır.

Problem

Bir maxSubarraySum funksiyası yazın. Bu funksiya tam ədədlərdən ibarət bir massiv və n adlı bir rəqəm qəbul etməlidir. Funksiya massivdə ardıcıl n elementin maksimum cəmini tapmalıdır.

Naiv həll

Bu üsul massivdəki bütün mümkün n uzunluqlu alt massivləri yoxlayır və onların cəmini hesablayır.

Zaman mürəkkəbliyi: O(n²)

function maxSubarraySum(array, num) {
  if (num > array.length) return null;

  let max = -Infinity;
  for (let i = 0; i < array.length - num + 1; i++) {
    let temp = 0;

    for (let j = 0; j < num; j++) {
      temp += array[i + j];
    }

    if (temp > max) {
      max = temp;
    }
  }

  return max;
}

maxSubarraySum([1, 2, 5, 2, 8, 1, 5], 4); // 17

Çatışmazlıqlar:

Hər bir alt massiv üçün n dəfə toplanma əməliyyatı aparırıq.
Böyük massivlər üçün performans çox aşağı olur.

Sliding window həlli

Bu üsulda bir pəncərə (window) istifadə edirik və onu hərəkət etdiririk.

Məntiq:

Əvvəlcə ilk n elementin cəmini hesablayırıq.
Sonra bu cəmi tədricən yeniləyirik:
- Yeni elementi əlavə edirik.
- Əvvəlki pəncərədən çıxan elementi çıxırıq.
Ən böyük cəmi tapırıq.

Zaman mürəkkəbliyi: O(n)

function maxSubarraySum(array, num) {
  let maxSum = 0;
  let tempSum = 0;
  if (num > array.length) return null;

  for (let j = 0; j < num; j++) {
    maxSum += array[j];
  }

  tempSum = maxSum;

  for (let i = num; i < array.length; i++) {
    tempSum = tempSum - array[i - num] + array[i];
    maxSum = Math.max(maxSum, tempSum);
  }

  return maxSum;
}

maxSubarraySum([1, 2, 5, 2, 8, 1, 5], 4); // 17

Üstünlüklər:

O(n²) əvəzinə O(n) mürəkkəbliklə işləyir.
Daha az yaddaş istifadə edir.
Böyük massivlər üçün daha effektivdir.

Nəticə

Sliding window nümunəsi ardıcıl verilənləri analiz edərkən çox güclü üsuldur. Bu metod sürətli və yaddaş baxımından effektiv həllər yaratmağa imkan verir.

Bu yanaşma aşağıdakı hallarda xüsusilə faydalıdır:
Ardıcıl ən böyük və ya ən kiçik məbləği tapmaq
Sətirlərdə və massivlərdə xüsusi ardıcıllıqları izləmək
Məlumat axınını optimallaşdırmaq

codex

Aşağıda LeetCode platformasında bu nümunə ilə həll edilə bilinən problemlərin siyahısı aşağıdakı kimidir. Əgər bildiyiniz problemlər varsa aşağıda əlavə edə bilərsiniz:

Bütün problemlərin siyahısını isə buradan baxa bilərsiz.