Next Greater Element I

Q: ما التعقيد الزمني للمسألة «العنصر الأكبر التالي I»؟

يعمل حل المكدس الرتيب في زمن O(n + m) ، حيث إن n هو طول nums2 و m هو طول nums1 . تُضاف كل قيمة من nums2 إلى المكدس وتُزال منه مرة واحدة كحد أقصى، ويُجرى بحث واحد في الخريطة لكل قيمة من nums1 . تستخدم الخريطة والمكدس مساحة O(n) . يستغرق المسح إلى اليمين انطلاقًا من كل قيمة زمنًا قدره O(n·m) .

سهلالمكدس الرتيب التجزئة

+10

لديك مصفوفتان من الأعداد الصحيحة المتميزة، nums1 وnums2، وتظهر كل قيمة في nums1 أيضًا في nums2. العنصر الأكبر التالي لقيمة x هو أول قيمة تقع إلى يمين x في nums2 وتكون أكبر من x، أو -1 إذا لم توجد مثل هذه القيمة.

أعِد مصفوفة تحتوي على العنصر الأكبر التالي لكل قيمة في nums1، وفق ترتيب القيم في nums1.

الدالة

nextGreaterElement(nums1: integer-array, nums2: integer-array) → integer-array

nums1integer-array: القيم المطلوب الإجابة عنها، وكلها موجودة في nums2
nums2integer-array: المصفوفة التي تبحث فيها إلى يمين كل قيمة
تُرجعinteger-array: العنصر الأكبر التالي لكل قيمة في nums1، أو -1، بترتيب nums1

القيود

1 ≤ nums1.length ≤ nums2.length ≤ 10⁴
0 ≤ nums1[i], nums2[i] ≤ 10⁴
جميع القيم في nums1 متميزة، وجميع القيم في nums2 متميزة.
تظهر كل قيمة من nums1 في nums2.

أمثلة

المدخلات: nums1 = [3, 8, 1]nums2 = [1, 6, 3, 8, 2]
المخرجات: [8, -1, 6]
الشرح: بعد الرقم 3 في nums2 يأتي الرقمان 8 و2، و8 هو أول رقم أكبر من 3. لا يأتي بعد 8 سوى 2، لذا تكون قيمة 8 هي -1. القيمة التي تأتي مباشرة بعد 1 هي 6، وهي أكبر بالفعل.

المدخلات: nums1 = [5, 2]nums2 = [2, 9, 5, 4]
المخرجات: [-1, 9]
الشرح: العدد 4 فقط هو الذي يأتي بعد 5، و4 أصغر، لذا تحصل 5 على ‎-1. القيمة التي تأتي مباشرةً بعد 2 هي 9. تتبع الإجابات ترتيب nums1، وليس ترتيب nums2.

+14 اختبارات مخفية عند الإرسال

سؤال إضافي

لكل موضع في nums2، هل يمكنك إرجاع عدد الخطوات إلى اليمين التي تفصل بينه وبين العنصر الأكبر التالي، باستخدام المرور الواحد نفسه؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

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

اعثر على كل قيمة وامسح باتجاه اليمين

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

نفّذ ما يقوله التعريف. بالنسبة إلى قيمة x في nums1، امشِ عبر nums2 حتى تصل إلى x. ثم واصل المشي وتوقّف عند أول قيمة أكبر من x. إذا وصلت إلى النهاية من دون العثور على واحدة، فالإجابة هي -1.

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

يكون هذا بطيئًا عندما تكون الإجابات بعيدة أو غير موجودة. إذا كانت nums2 تنازلية، فلن يعثر أي مسح على قيمة أكبر، وستواصل كل قيمة في nums1 السير حتى النهاية. ومع وجود m قيمة في nums1 وn قيمة في nums2، يصل ذلك إلى m × n خطوة: 10^8 عندما تحتوي كلتا المصفوفتين على 10^4 قيمة. كما أن كل مسح يقطع جزءًا سبق أن قطعته عمليات المسح السابقة.

الخوارزمية

كرّر المرور على كل قيمة x من nums1.
اعثر على الفهرس j حيث تكون nums2[j] مساوية لـ x.
امسح nums2 بدءًا من j+1 وتوقّف عند أول قيمة أكبر من x.
أضف تلك القيمة، أو -1 إذا وصل المسح إلى النهاية.
أعِد الإجابات التي جُمعت.

def nextGreaterElement(nums1, nums2):
    result = []
    for x in nums1:
        j = 0
        while nums2[j] != x:
            j += 1
        answer = -1
        for k in range(j + 1, len(nums2)):
            if nums2[k] > x:
                answer = nums2[k]
                break
        result.append(answer)
    return result

مكدّس أحادي الاتجاه وخريطة تجزئة

الفكرة

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

مرّ على nums2 = [1, 6, 3, 8, 2]. أضف 1 إلى المكدس. ثم تصل 6 وتتغلب على 1، لذا ترتبط 1 بـ 6؛ أضف 6 إلى المكدس. ثم تصل 3، ولا تتغلب على 6، فتُضاف إلى الأعلى: يصبح المكدس [6, 3]. ثم تزيل 8 القيمتين 3 و6، لذا ترتبط كلتاهما بـ 8؛ أضف 8 إلى المكدس. ثم تُضاف 2. يصبح المكدس في النهاية [8, 2]، ولا إجابة لهاتين القيمتين. بالنسبة إلى nums1 = [3, 8, 1]، تعطي الخريطة [8, -1, 6].

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

تُضاف كل قيمة من nums2 مرة واحدة، وتُزال مرة واحدة على الأكثر، لذا تنفّذ الحلقة الداخلية ما لا يزيد على n عمليات إزالة إجمالًا خلال المرور كله. ومع عمليات البحث الـ m، يكون الزمن O(n + m). الخريطة هي ما يربط المصفوفتين: القيم متميزة، لذا تصلح القيمة مفتاحًا، حتى وإن ظهرت في مواضع مختلفة في nums1 وnums2. يستخدم حلّا C وR مصفوفةً من 10^4+1 خانات مفهرسة حسب القيمة بوصفها خريطة، وهذا ينجح لأن أي قيمة لا تتجاوز 10^4.

الخوارزمية

أنشئ خريطة فارغة ومكدسًا فارغًا.
لكل قيمة في nums2، أزل من أعلى المكدس كل قيمة أصغر، واربطها بالقيمة الحالية في الخريطة.
أضف القيمة الحالية إلى المكدس.
لكل قيمة في nums1، أرجِع الإجابة المرتبطة بها، أو -1 إن لم تكن لها إجابة.

def nextGreaterElement(nums1, nums2):
    next_greater = {}
    stack = []  # values still waiting for a greater one, decreasing from bottom to top
    for value in nums2:
        # value is the first greater value to the right of every smaller value on the stack.
        while stack and stack[-1] < value:
            next_greater[stack.pop()] = value
        stack.append(value)
    # Whatever is still on the stack has no greater value to its right.
    return [next_greater.get(x, -1) for x in nums1]

أخطاء شائعة وحالات حدّية

الشيفرة الخاصة بالمكدّس قصيرة؛ أما الأخطاء فتكون فيما تسجّله وأين تبحث.

تسجيل أكبر قيمة إلى اليمين بدلًا من أول قيمة أكبر. في nums2 = [3, 5, 1, 2, 4, 9, 0] الإجابة عن 1 هي 2، وليست 9.
إرجاع الإجابات بترتيب nums2، أو لكل قيمة في nums2. تحتوي النتيجة على مدخلة واحدة لكل قيمة في nums1، وبترتيبها.
إرجاع فهرس بدلًا من قيمة. المسألة تطلب القيمة الأكبر نفسها.
قراءة nums2 عند الفهرس الذي تشغله قيمة في nums1. تقع القيمة نفسها في مواضع مختلفة في المصفوفتين؛ لذا ابحث عنها بحسب قيمتها، وهذا هو الغرض من الخريطة.
نسيان القيم المتبقية في المكدّس عند النهاية. لم تصادف هذه القيم قيمة أكبر، لذا فإجابتها هي -1؛ والبحث في الخريطة دون قيمة افتراضية يفشل أو لا يعيد شيئًا لهذه القيم.
البحث إلى اليسار، أو الالتفاف إلى بداية nums2. تُحتسب القيم الموجودة إلى اليمين فقط، والمصفوفة لا تلتف.

أسئلة شائعة4

ما التعقيد الزمني للمسألة «العنصر الأكبر التالي I»؟

يعمل حل المكدس الرتيب في زمن O(n + m)، حيث إن n هو طول nums2 وm هو طول nums1. تُضاف كل قيمة من nums2 إلى المكدس وتُزال منه مرة واحدة كحد أقصى، ويُجرى بحث واحد في الخريطة لكل قيمة من nums1. تستخدم الخريطة والمكدس مساحة O(n). يستغرق المسح إلى اليمين انطلاقًا من كل قيمة زمنًا قدره O(n·m).

ما هو المكدس الرتيب؟

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

لماذا يحتاج عنصر أكبر لاحقًا I إلى خريطة تجزئة؟

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

ما الذي يتغير إذا كانت nums2 دائرية؟

بعد ذلك، يمكن أن يستمر البحث عن قيمة أكبر بدءًا من بداية المصفوفة. نفّذ المرور نفسه بالمكدس على المصفوفة مرتين، باستخدام الفهرس i % n للقيم i من 0 إلى 2n-1، وأضف القيم إلى المكدس خلال الجولة الأولى فقط. القيم التي لا تزال في المكدس بعد الجولتين ليس لها قيمة أكبر في أي موضع، لذا تكون إجاباتها -1.

Python

def nextGreaterElement(nums1, nums2):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

nums1 = [3, 8, 1]
nums2 = [1, 6, 3, 8, 2]

المتوقع

[8, -1, 6]