أقصى قيمة في النافذة المنزلقة باستخدام Deque
الحفاظ على أطراف النافذة في O(n)
أقصى قيمة في النافذة المنزلقة باستخدام Deque درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 4 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 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) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «أقصى قيمة في النافذة المنزلقة باستخدام Deque»؟
الحفاظ على أطراف النافذة في O(n) تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 4 من أصل 4.
كم من الوقت يستغرق درس «أقصى قيمة في النافذة المنزلقة باستخدام Deque»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- المكدسات لمطابقة الأقواس
- المكدس الرتيب: العنصر الأكبر التالي
- قوائم الانتظار وcollections.deque
- أقصى قيمة في النافذة المنزلقة باستخدام Deque