مجاميع نافذة ثابتة الحجم

تطلب مسائل كثيرة حساب مجموع كل كتلة من k عناصر متتالية. إعادة حساب كل كتلة من الصفر تهدر الوقت، ويمكنكم تنفيذ ذلك بكفاءة أكبر. 🪟

تجمع الفكرة الساذجة كل نافذة طولها k على حدة. وهذا يكرر العمل وتبلغ كلفته O(n × k)، وهو بطيء جدًا للمدخلات الكبيرة.

تتداخل النوافذ المتجاورة تداخلًا شبه كامل. وعند التحرك خطوة واحدة إلى اليمين، لا نحتاج إلا إلى إزالة العنصر الموجود في أقصى اليسار وإضافة عنصر جديد من اليمين.

ابدؤوا بجمع أول k عناصر مرة واحدة. فهذا المجموع المفرد هو الأساس الذي ستواصلون تحديثه أثناء انزلاق النافذة إلى الأمام.

لتحريك النافذة، أضيفوا العنصر الداخل واطرحوا العنصر الخارج. وهكذا تبقى كلفة كل خطوة ثابتة وتساوي O(1).

بعد كل انزلاق، حدّثوا ما تحتاجون إليه، مثل أكبر مجموع نافذة ظهر حتى الآن. فقيمة النافذة تكون متاحة فورًا دائمًا.

تلمسون كل عنصر لإضافته، ثم تلمسونه مرة أخرى لإزالته، لذلك تكون عملية المرور كاملة بتعقيد O(n). وهذا يتعامل بسهولة مع القيود الكبيرة.

العنصر الذي يغادر النافذة هو a[i - k]، وليس a[i - 1]. ويُعد ضبط هذا الإزاحة بالشكل الصحيح الخطأ الأكثر شيوعًا في النوافذ ثابتة الطول.

هل تحتاجون إلى متوسط النافذة الأكبر بدلًا من مجموعها؟ اقسموا مجموع النافذة المتتبَّع على k فحسب. ولا يتغير منطق النافذة المنزلقة إطلاقًا.

إذا كانت المصفوفة أقصر من k، فلن توجد نافذة كاملة. افحصوا len(a) مقارنةً بـ k مسبقًا وأعيدوا النتيجة مبكرًا لتجنب خطأ الفهرسة.

استخدموا هذا النمط عندما يكون طول النافذة ثابتًا وتستطيعون دمج القيم بكلفة منخفضة، مثل المجاميع أو أعداد العناصر أو الإحصاءات الجارية البسيطة.

تحرّكون نافذة بحجم k خطوة واحدة إلى اليمين عبر مصفوفة.

هيّئوا النافذة الأولى مرة واحدة، ثم أضيفوا واطرحوا في كل خطوة لتحريكها بتعقيد O(1). ويمر الفحص الكامل ذي الحجم الثابت في زمن خطي. ✅