أول عنصر أكبر إلى اليمين: مكدس المواضع المنتظرة وشرط التعادل

السؤال عن أول موضع لا عن أكبر قيمة

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

تعرض مسألة الأيام الأدفأ في LeetCode نموذج انتظار أول قيمة أعلى في المستقبل، بينما يعرض دليل USACO نموذجًا قريبًا يبحث عن الأصغر السابق بمكدس رتيب. نستخدم هنا صياغة عددية عامة، بأعداد صحيحة عادية وتكرارات ممكنة، ثم نتتبع مكدسًا من مواضع العناصر التي لم تجد جوابها بعد. لا نقيس حرارة فعلية ولا نتنبأ ببيانات لم تصل؛ جميع عناصر المثال معلومة، وما نفعله هو تحليل ترتيبها. كما أن القائمة غير دائرية: بعد آخر عنصر نتوقف، ولا نعود إلى البداية للعثور على جواب. هذه الحدود تجعل معنى الانتظار والفشل قابلًا للتحقق دون افتراضات إضافية.

نموذج انتظار الأدفأ، المكدس الرتيب في سؤال قريب، عمليات القائمة كمكدس.

المثال الرئيسي ونتيجته المفصلة

لدينا ثمانية عناصر، قيمها بالترتيب (4,2,2,5,1,5,3,6)، ومواضعها تبدأ من الصفر وتنتهي عند سبعة. العنصر الأول قيمته أربعة، وأول أكبر منه يقع عند الموضع ثلاثة بقيمة خمسة. العنصران عند الموضعين واحد واثنين قيمتهما اثنان، ويجد كلاهما أول قيمة أكبر عند الموضع ثلاثة أيضًا. القيمة خمسة عند الموضع ثلاثة لا تجد جوابها في الخمسة الثانية عند الموضع خمسة لأنهما متساويتان؛ جوابها هو الستة عند الموضع سبعة. أما الواحد عند الموضع أربعة فيجد الخمسة التالية عند الموضع خمسة مباشرة.

الخمسة عند الموضع خمسة والثلاثة عند الموضع ستة يجدان الستة عند الموضع سبعة، بينما الستة الأخيرة لا تجد عنصرًا بعدها. يكون متجه مواضع الإجابات (3,3,3,7,5,7,7,None). وإذا أردنا مقدار الانتظار بالمواضع، نطرح موضع العنصر من موضع جوابه، فيصبح المتجه (3,2,1,4,1,2,1,0)، حيث جعلنا الصفر علامة غياب في متجه الانتظار فقط. هذه الأعداد لا تمثل فروق القيم؛ مثلًا انتظار الأربعة ثلاث خطوات موضعية رغم أن الزيادة العددية إلى الخمسة واحدة. وتبقى مواضع العناصر المكررة منفصلة حتى حين تتساوى إجاباتها.

البحث المباشر مرجع واضح للمراجعة

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

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

ماذا يخزن مكدس المنتظرين؟

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

عند وصول قيمة جديدة، نقارنها بقيمة موضع القمة. إن كانت الجديدة أكبر تمامًا، فقد وجد صاحب القمة جوابه، فنخرجه ونكتب له الموضع الحالي. نعيد المقارنة مع القمة التالية لأن العنصر الجديد قد يحل عدة انتظار في الزيارة نفسها. نتوقف حين يفرغ المكدس أو تصبح قيمة القمة أكبر من الجديدة أو مساوية لها، ثم نضيف الموضع الحالي إلى المنتظرين. تدعم قائمة Python هذه العمليات بإضافة إلى النهاية وقراءة آخر عنصر وإزالته من النهاية؛ نتحقق من وجود قمة قبل قراءتها، ولا نزيل من المقدمة لأن العقد هنا يتعامل مع آخر منتظر.

أول ثلاث زيارات تبني انتظارًا دون جواب

عند الموضع صفر تصل القيمة أربعة ولا يوجد منتظر سابق، فنضيف الموضع صفر. تصل القيمة اثنان عند الموضع واحد، فلا تحل انتظار الأربعة لأنها أصغر منها، ثم نضيف الموضع واحد. تصل القيمة اثنان مرة أخرى عند الموضع اثنين، ولا تحل انتظار الاثنان السابقة لأن شرط الجواب أكبر تمامًا. نضيف الموضع اثنين أيضًا، فيصبح المكدس (0,1,2)، وقيمه أربعة ثم اثنان ثم اثنان. هذه الحالة توضح أن وصف المكدس بأنه غير متزايد أدق من وصفه بأنه متناقص تمامًا في هذا التنفيذ الذي يبقي المساويات منتظرة.

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

الخمسة الأولى تحل ثلاثة مواضع

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

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

الخمسة الثانية تبقي التعادل ثم الستة تنهيه

بعد إضافة الموضع ثلاثة، تصل القيمة واحد عند الموضع أربعة. لا تتجاوز الخمسة، فنضيف موضعها إلى المكدس، ليصبح (3,4). تصل الخمسة الثانية عند الموضع خمسة، فتخرج الواحد عند أربعة وتكتب له الجواب خمسة. لكن الخمسة الأولى عند ثلاثة تبقى لأن الخمسة الحالية مساوية لها. نضيف الموضع خمسة، فيصبح المكدس (3,5)، وقيمتا الموضعين خمسة وخمسة. تصل الثلاثة عند الموضع ستة، فلا تتجاوز الخمسة في القمة، فنضيفها ويصبح المكدس (3,5,6). لا يمنع تساوي القيمتين من حفظ موضعيهما المختلفين.

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

تغيير المقارنة يجعل السؤال غير صارم

لنأخذ القائمة (5,5,6). في السؤال الصارم لا تجيب الخمسة الثانية عن الخمسة الأولى، بل تنتظران الستة عند الموضع اثنين، فتكون الإجابات (2,2,None). إذا استبدلنا شرط الجديدة أكبر تمامًا بشرط الجديدة أكبر أو مساوية، فإن الموضع صفر يخرج عند وصول الموضع واحد، وتصبح الإجابات (1,2,None). هذا الناتج صحيح لسؤال آخر يطلب أول قيمة لا تقل عن الحالية، لكنه خاطئ للسؤال الذي اخترناه. ليس تغيير علامة المقارنة تحسينًا داخليًا محايدًا؛ إنه تغيير معنى الشاهد المقبول.

لا تختصر المساويات في موضع واحد عندما يحتاج كل ظهور إلى إجابة مستقلة. يمكن لبعض الأسئلة الأخرى استخدام قواعد حذف مختلفة، لكن عليك اشتقاقها من اتجاه البحث والشرط المطلوب، لا نسخها من مثال قريب. نموذج الأصغر السابق في دليل USACO يحذف قيمًا عند قدوم عنصر أصغر أو مساوٍ ليحافظ على مرشحين للسؤال السابق؛ هنا نحن نغلق أسئلة منتظرة عند وصول عنصر أكبر، ونبقي التعادل. التشابه في وجود مكدس لا يجعل الدور نفسه ولا اتجاه المقارنة نفسه. اكتب بجوار الحلقة ما الذي يمثله المحذوف، وهل حذفناه بعد تثبيت جوابه أم استبعدناه من الترشيح.

عرض الرسم بالحجم الكامل

دليل الأولوية الموضعية وحفظ شرط المكدس

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

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

لماذا لا تجعل الحلقة الداخلية العمل تربيعيًا؟

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

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

الغياب والفهرس والقيمة ثلاث نتائج مختلفة

استعملنا None في متجه المواضع عندما لا يوجد جواب. لا نستعمل صفرًا في هذا المتجه بوصفه غيابًا عامًا، لأن الصفر موضع صالح في القوائم، حتى لو كان اتجاه اليمين يجعل جواب عنصر غير سالب يقع بعده. كما لا نعيد قيمة سالبة معينة للدلالة على الغياب إذا سمحنا للمدخل بأعداد سالبة. في القائمة (-2,-1,-3) يكون جواب العنصر الأول الموضع واحد وقيمته سالب واحد؛ إذا عرضنا القيمة سالب واحد بوصفها علامة غياب أيضًا، فلن نستطيع التمييز بين شاهد حقيقي وبين حالة لم تجد شاهدًا. تخزين موضع اختياري يفصل الحالتين بوضوح.

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

الفراغ والحدود والاختبارات المنفذة

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

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

استعمال النتيجة دون توسيع السؤال ضمنًا

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

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