Sliding Window
النافذة المنزلقة Sliding Window
النافذة المنزلقة تحسب نتيجة على نطاقات متتالية من مصفوفة بكفاءة، عبر تحريك نافذة (بحجم ثابت أو متغيّر) بدل إعادة حساب كل نطاق من الصفر.
بدل إعادة حساب المجموع (أو أي قيمة تراكمية) لكل نافذة فرعية بشكل منفصل (O(n×k))، تُحدَّث النافذة تدريجيًا: يُضاف العنصر الجديد الداخل ويُطرح العنصر الخارج، فيصبح التحديث O(1) لكل خطوة والإجمالي O(n).
الصياغة
window_sum = sum(arr[:k])
best = window_sum
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k] # أضف الجديد، اطرح القديم
best = max(best, window_sum)📄 مثال
def max_sum_fixed_window(arr, k):
window_sum = sum(arr[:k])
best = window_sum
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k]
best = max(best, window_sum)
return best
print(max_sum_fixed_window([2, 1, 5, 1, 3, 2], 3)) # 9 (5+1+3)أهم النقاط
| النقطة | الوظيفة |
|---|---|
| التعقيد الزمني | O(n) — بدل O(n × k) بإعادة حساب كل نافذة من الصفر |
| التعقيد المكاني | O(1) عادةً (نافذة بحجم ثابت) أو O(k) (نافذة بحجم متغيّر تحتاج تتبّع محتوى) |
| نوعان | نافذة بحجم ثابت (k معروف مسبقًا)، أو نافذة بحجم متغيّر (تتوسّع/تنكمش حسب شرط) |
💡 نصائح عملية
- أي مسألة تسأل عن 'أطول/أقصر متتالية فرعية تحقّق شرطًا' أو 'أكبر/أصغر مجموع لنافذة بحجم k' — النافذة المنزلقة غالبًا الحل الأمثل
⚠️ أخطاء شائعة
- إعادة حساب مجموع النافذة بالكامل من الصفر بكل خطوة (حلقة داخل حلقة) بدل تحديثه تدريجيًا — يفقد الفائدة الأساسية للتقنية ويعيدك لتعقيد O(n × k)
خصائص ذات صلة
🎓 تريد فهم الصورة الكاملة خطوة بخطوة؟ ابدأ من مسار DSA الكامل بالعربي.