أقصى قيمة في النافذة المنزلقة باستخدام Deque
الحفاظ على أطراف النافذة في O(n)
أقصى قيمة في النافذة المنزلقة باستخدام Deque درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 4 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
أكبر قيمة في النافذة المنزلقة
مع إعطائك مصفوفة وحجم نافذة k، تريد إيجاد أكبر قيمة في كل نافذة أثناء انزلاقها إلى اليمين. وتستغرق الطريقة الساذجة O(n مضروبًا في k).
وعد بسرعة أكبر
باستخدام deque رتيب، يمكنك الإجابة عن كل نافذة في زمن إجمالي O(n)، عبر المرور على المصفوفة مرة واحدة فقط.
خزّن الفهارس مجددًا
احتفظ بـ الفهارس في deque لا بالقيم. إذ تتيح لك الفهارس التحقق مما إذا كانت المقدمة قد خرجت من النافذة الحالية.
from collections import deque
dq = deque()
res = []حافظ على التناقص
يحافظ deque على ترتيب تنازلي حسب القيمة من المقدمة إلى المؤخرة، ولذلك يشير فهرس المقدمة دائمًا إلى القيمة العظمى في النافذة.
أزل العناصر الأصغر من المؤخرة
قبل إضافة الفهرس i، أزل من المؤخرة ما دامت تلك القيم أصغر، لأنها لا يمكن أن تكون القيمة العظمى مستقبلًا.
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()أضف الفهرس الجديد
بعد التخلص من العناصر الأضعف في المؤخرة، استخدم append لإضافة الفهرس الحالي. ويبقى ترتيب deque صحيحًا للخطوات التالية.
dq.append(i)أخرج المقدمة القديمة
إذا خرج فهرس المقدمة من النافذة، فاستخدم popleft لإزالته. تبدأ نافذة حجمها k عند الفهرس i ناقص k زائد 1.
if dq[0] <= i - k:
dq.popleft()سجّل كل قيمة عظمى
بمجرد اكتمال أول نافذة عند الفهرس k ناقص 1، تحمل مقدمة deque الإجابة لكل موضع تالٍ.
if i >= k - 1:
res.append(nums[dq[0]])انتبه إلى ترتيب الإزالة
أخرج المقدمة القديمة قبل قراءة الإجابة. وإلا فقد تسجّل قيمة عظمى غادرت النافذة بالفعل.
لماذا يبقى الزمن خطيًا
تُضاف كل فهرس وتُزال مرة واحدة على الأكثر، لذا تكون كلفة deque متوسطة على المدى الطويل بمقدار O(1) لكل خطوة وO(n) إجمالًا.
النافذة الدنيا، الفكرة نفسها
لإيجاد القيمة الدنيا في نافذة منزلقة، اجعل deque متزايدًا بدلًا من ذلك. ما عليك إلا عكس المقارنة عند تقليص المؤخرة.
while dq and nums[dq[-1]] >= nums[i]:
dq.pop()تحقق سريع
في مسألة القيمة العظمى ضمن نافذة منزلقة، ماذا تحتوي مقدمة deque الرتيب؟
مراجعة: deque يتفوّق في النوافذ
حافظت على deque تنازلي من الفهارس: قلّص العناصر الصغيرة من المؤخرة، وأخرج المقدمة القديمة، واقرأ المقدمة للحصول على قيمة عظمى لكل نافذة في O(n). 🏆
الأسئلة الشائعة
هل درس «أقصى قيمة في النافذة المنزلقة باستخدام Deque» مجاني؟
نعم — نص درس «أقصى قيمة في النافذة المنزلقة باستخدام Deque» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «أقصى قيمة في النافذة المنزلقة باستخدام Deque»؟
الحفاظ على أطراف النافذة في O(n) تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 4 من أصل 4.
كم من الوقت يستغرق درس «أقصى قيمة في النافذة المنزلقة باستخدام Deque»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- المكدسات لمطابقة الأقواس
- المكدس الرتيب: العنصر الأكبر التالي
- قوائم الانتظار وcollections.deque
- أقصى قيمة في النافذة المنزلقة باستخدام Deque