المكدس الرتيب: العنصر الأكبر التالي
الإجابة عن استعلامات المدى في مرور واحد
المكدس الرتيب: العنصر الأكبر التالي درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 2 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
مسألة العنصر الأكبر التالي
لكل عدد، تريد أول قيمة أكبر منه إلى يمينه. تستغرق القوة الغاشمة O(n²)، لكن المكدس الرتيب يحلها في مرور واحد.
ماذا يعني رتيب
يحافظ المكدس الرتيب على قيمه بترتيب محدد، وهو هنا ترتيب تنازلي، ولذلك نعرف أن إجابة ظهرت فور اختلال ذلك الترتيب.
خزّن الفهارس لا القيم
أدخل الفهارس بدلًا من الأعداد نفسها. وبهذا تعرف الموضع الذي يجب ملؤه بالضبط عند ظهور عنصر أكبر.
stack = []
ans = [-1] * len(nums)مرّر من اليسار إلى اليمين
كرّر على المصفوفة مرة واحدة. عند كل موضع، إما أن تخرج العناصر التي حُسمت أو تدخل الفهرس الحالي لاستخدامه لاحقًا.
for i in range(len(nums)):أخرج العناصر الأصغر
ما دامت القيمة الحالية تتفوق على القيمة عند فهرس القمة، فهذا الفهرس قد وجد أخيرًا عنصره الأكبر التالي.
while stack and nums[i] > nums[stack[-1]]:سجّل الإجابة
أخرج فهرس القمة واجعل إجابته القيمة الحالية. يُحسم كل فهرس مرة واحدة بالضبط، مما يحافظ على كون العمل خطيًا.
j = stack.pop()
ans[j] = nums[i]أدخل وتابع
بعد حسم كل العناصر الأصغر، أدخل الفهرس الحالي حتى ينتظر عنصره الأكبر المستقبلي.
stack.append(i)العناصر المتبقية لا تملك إجابة
الفهارس التي تبقى في المكدس عند النهاية لم تواجه قيمة أكبر قط. وتحتفظ بقيمتها الافتراضية -1، ما يعني عدم وجود مثل هذه القيمة.
لماذا الزمن O(n)
يُضاف كل فهرس مرة واحدة ويُزال مرة واحدة. لذلك، حتى مع وجود حلقة while الداخلية، يبقى إجمالي العمل خطيًا على امتداد الفحص كله.
اعكسها للعثور على الأصغر التالي
هل تحتاج إلى العنصر الأصغر التالي بدلًا من ذلك؟ حافظ على كون المكدس متزايدًا عبر عكس المقارنة من أكبر من إلى أصغر من.
while stack and nums[i] < nums[stack[-1]]:نمط لا حيلة مؤقتة
تعيد استعلامات المدى وأسعار الأسهم ومساحات المدرجات استخدام هذه الفكرة. ويُعدّ المكدس الرتيب نمطًا أساسيًا في المسابقات يستحق الحفظ.
تحقق سريع
تحل مسألة العنصر الأكبر التالي باستخدام مكدس رتيب. لماذا يكون الزمن الإجمالي خطيًا؟
مراجعة: مرور واحد، وإجابات كثيرة
استخدمت مكدسًا رتيبًا تنازليًا من الفهارس للعثور على العناصر الأكبر التالية في O(n). ويفتح هذا النمط الباب أمام كثير من مسائل المدى. 🚀
الأسئلة الشائعة
هل درس «المكدس الرتيب: العنصر الأكبر التالي» مجاني؟
نعم — نص درس «المكدس الرتيب: العنصر الأكبر التالي» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «المكدس الرتيب: العنصر الأكبر التالي»؟
الإجابة عن استعلامات المدى في مرور واحد تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 2 من أصل 4.
كم من الوقت يستغرق درس «المكدس الرتيب: العنصر الأكبر التالي»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- المكدسات لمطابقة الأقواس
- المكدس الرتيب: العنصر الأكبر التالي
- قوائم الانتظار وcollections.deque
- أقصى قيمة في النافذة المنزلقة باستخدام Deque