Daily Temperatures

Q: ما هو التعقيد الزمني لمسألة درجات الحرارة اليومية؟

يعمل حل المكدس الرتيب بزمن O(n) ومساحة إضافية O(n) . يُدفَع كل يوم إلى المكدس مرة واحدة، ويُزال منه مرة واحدة على الأكثر، لذا تُنفَّذ الحلقة الداخلية n مرات على الأكثر خلال المرور بأكمله. يستغرق الفحص إلى الأمام بدءًا من كل يوم زمنًا قدره O(n²) ، أي نحو 5 × 10^7 مقارنةً لـ 10^4 يوم دون وجود يوم أدفأ.

Q: لماذا يخزّن المكدس الفهارس بدلًا من درجات الحرارة؟

الإجابة عن يوم ما هي مسافة، today - day ، لذا تحتاج إلى موضع اليوم. ويخبرك الفهرس أيضًا بأي خانة في مصفوفة الإجابات تملؤها عند إخراج اليوم من المكدس. ولا يفصلك عن درجة الحرارة سوى عملية وصول واحدة، وهي temperatures[day] ، لذا فإن تخزينها أيضًا لا يضيف شيئًا.

Q: هل يمكن حل مسألة درجات الحرارة اليومية دون استخدام مكدس؟

نعم. تحرّك من اليوم الأخير إلى اليوم الأول، وابدأ لليوم i من j = i+1 . ما دام اليوم j ليس أدفأ، فانتقل إلى اليوم الذي تشير إليه إجابة j ، أي j + answer[j] ؛ وإذا كانت answer[j] تساوي 0، فلا يوجد يوم أدفأ، وتكون إجابة اليوم i هي 0 أيضًا. تتخطى هذه القفزات كل يوم لا يمكن أن يكون هو الإجابة، ولا يُتخطى كل يوم إلا مرة واحدة على الأكثر، ويبقى الزمن O(n) من دون استخدام ذاكرة سوى مصفوفة الإجابات.

متوسطالمكدس الرتيب

+10

تحصل على درجة حرارة كل يوم ضمن سلسلة من الأيام: temperatures[i] هي درجة الحرارة في اليوم i. لكل يوم، احسب عدد الأيام التي عليك انتظارها بعده حتى يحلّ يوم أكثر حرارة منه تمامًا. إذا لم يأتِ يوم أكثر حرارة لاحقًا، فمدة الانتظار لذلك اليوم هي 0.

أعِد مصفوفة بالطول نفسه، حيث تكون القيمة عند الموضع i هي مدة الانتظار لليوم i.

الدالة

dailyTemperatures(temperatures: integer-array) → integer-array

temperaturesinteger-array: درجة حرارة كل يوم، بالترتيب
تُرجعinteger-array: لكل يوم، عدد الأيام المتبقية حتى يوم أكثر دفئًا، أو 0 إذا لم يأتِ يوم كهذا

القيود

1 ≤ temperatures.length ≤ 10⁴
30 ≤ temperatures[i] ≤ 100
تعني «أكثر دفئًا» أن تكون الحرارة أعلى تمامًا: لا يُحتسب يوم لاحق له درجة الحرارة نفسها.

أمثلة

المدخلات: temperatures = [71, 69, 72, 70, 70, 75, 68]
المخرجات: [2, 1, 3, 2, 1, 0, 0]
الشرح: درجة حرارة اليوم 0 هي 71، وأول يوم أدفأ هو اليوم 2 بدرجة حرارة 72، لذا ينتظر يومين. درجة الحرارة في اليومين 3 و4 هي 70: درجة الحرارة 70 الثانية ليست أدفأ، لذا ينتظر اليوم 3 حتى اليوم 5 بدرجة حرارة 75، أي يومين. لا توجد درجة حرارة أعلى من 75 أو 68 بعد ذلك، لذا تكون النتيجة 0 لكليهما.

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

سؤال إضافي

تأخذ درجات الحرارة 71 قيمة فقط، من 30 إلى 100. كيف يمكن لجدول مفهرس بدرجة الحرارة أن يجيب عن كل يوم في مرور واحد من اليمين إلى اليسار، وما تكلفة هذا المرور؟

الحل

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

تابع المسح إلى الأمام بدءًا من كل يوم

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

الفكرة

اتبع ما يقوله السؤال. في اليوم i، انظر إلى اليوم i+1، ثم i+2، وهكذا، وتوقف عند أول يوم تكون درجة حرارته أعلى بشكل صارم. المسافة j-i هي الإجابة. إذا وصلت إلى النهاية دون أن تجد يومًا كهذا، فتبقى الإجابة 0.

هذا صحيح لأن المسح يزور الأيام اللاحقة بالترتيب، لذا فإن أول يوم أدفأ يصادفه هو أول يوم أدفأ موجود. والتوقف عنده مباشرة مهم أيضًا: فالمسح الذي يستمر سيُسجّل آخر يوم أدفأ بدلًا منه.

يكون هذا بطيئًا عندما تكون الأيام الأدفأ بعيدة أو غير موجودة. إذا كانت درجات الحرارة في الأيام البالغ عددها 10^4 متساوية، فلن يتوقف أي مسح مبكرًا: يفحص اليوم 0 عدد 9,999 يومًا، ويفحص اليوم 1 عدد 9,998 يومًا، ويبلغ الإجمالي نحو n²/2 = 5 × 10^7 مقارنة. كما تتداخل عمليات المسح: يمر اليوم 1 تقريبًا على المسار نفسه الذي مر به اليوم 0، ولا يستفيد من ذلك.

الخوارزمية

أنشئ مصفوفة إجابة من الأصفار، بعنصر واحد لكل يوم.
لكل يوم i، افحص j من i+1 حتى اليوم الأخير.
عند أول j يحقق temperatures[j] > temperatures[i]، خزّن j-i وأوقف الفحص.
أعِد مصفوفة الإجابة؛ الأيام التي لم يعثر فحصها على أي شيء تحتفظ بالقيمة 0.

def dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n
    for i in range(n):
        for j in range(i + 1, n):
            if temperatures[j] > temperatures[i]:
                answer[i] = j - i  # the first warmer day, so stop here
                break
    return answer

مكدّس رتيب لأيام الانتظار

الفكرة

اعكس السؤال. بدلًا من أن تسأل كل يوم عمّا يأتي بعده، مرّ على الأيام مرة واحدة، ودع كل يوم جديد يجيب عن الأيام السابقة التي تكون حرارته أعلى منها. احتفظ بالأيام التي لم تجد إجابة بعد في مكدّس على هيئة فهارس. عندما يحلّ اليوم الحالي، يكون كل يوم منتظر أبرد من اليوم الحالي قد وجد أول يوم أدفأ منه: اليوم الحالي. أخرج كلًّا منها من المكدّس واكتب today - day كإجابته. ثم أضف اليوم الحالي إلى المكدّس، إذ ينتظر الآن يومه الأدفأ.

مرّ على [71, 69, 72, 70, 70, 75, 68]. يُضاف اليوم 0 (71) إلى المكدّس. اليوم 1 (69) ليس أدفأ من 71، لذا يُضاف إلى قمته: يحتوي المكدّس على الأيام [0, 1]. يُخرج اليوم 2 (72) اليوم 1 (انتظار 1)، ثم اليوم 0 (انتظار 2)، ثم يُضاف إلى المكدّس. يُضاف اليومان 3 و4 (70 و70)؛ ولا يُخرج 70 الثاني 70 الأول، لأن تساوي الحرارة لا يعني أن الجو أدفأ. يُخرج اليوم 5 (75) اليوم 4 (انتظار 1)، واليوم 3 (انتظار 2)، واليوم 2 (انتظار 3). يُضاف اليوم 6 (68) إلى المكدّس. يظل اليومان 5 و6 منتظرين في النهاية، لذا تبقى قيمتهما 0. الإجابة هي [2, 1, 3, 2, 1, 0, 0].

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

يحتوي المكدّس على الفهارس، لا درجات الحرارة، لأن الإجابة تمثّل مسافة، ولأنك تحتاج إلى معرفة الخانة التي عليك ملؤها في الإجابة. اقرأ درجة الحرارة باستخدام temperatures[day]. يُضاف كل يوم مرة واحدة، ويُخرج مرة واحدة على الأكثر، لذا لا يتجاوز مجموع مرات الإخراج خلال المرور كله n، ويكون الزمن الإجمالي O(n)، حتى لو استطاع يوم واحد إخراج أيام كثيرة.

الخوارزمية

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

def dailyTemperatures(temperatures):
    answer = [0] * len(temperatures)
    waiting = []  # indices of days with no warmer day yet, colder toward the top
    for today, temp in enumerate(temperatures):
        # Today is the first warmer day for every colder day on top of the stack.
        while waiting and temperatures[waiting[-1]] < temp:
            day = waiting.pop()
            answer[day] = today - day
        waiting.append(today)
    # Days still waiting never get a warmer day and keep their 0.
    return answer

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

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

إزالة العناصر عند >= بدلًا من >. اليوم الذي تكون فيه درجة الحرارة مساوية ليس أكثر دفئًا. في [71, 69, 72, 70, 70, 75, 68]، ينتظر اليوم 3 مدة يومين حتى اليوم الذي تبلغ فيه الحرارة 75، وليس يومًا واحدًا حتى اليوم الثاني الذي تبلغ فيه الحرارة 70.
إضافة درجات الحرارة بدلًا من الفهارس. الإجابة هي المسافة بالأيام، وتحتاج إلى الفهرس لحسابها ومعرفة الخانة التي يجب ملؤها.
استخدام if حيث تحتاج إلى while. يمكن ليوم واحد دافئ أن يجيب عن أيام انتظار كثيرة دفعة واحدة: ففي المثال الأول، تجيب 75 عن ثلاثة أيام.
إرجاع درجة الحرارة الأعلى أو فهرس اليوم الأكثر دفئًا. المخرَج هو عدد الأيام التي تنتظرها، j-i.
ترك الأيام التي لا تزال في المكدس دون تعيين إجابات لها. إجاباتها هي 0؛ في C، خصّص الذاكرة للإجابة باستخدام calloc أو املأها، لأن ذاكرة malloc تحتوي على قيم غير محددة.
السماح للمسح الأمامي بتجاوز أول يوم أكثر دفئًا. من دون break، يسجّل آخر يوم أكثر دفئًا بدلًا من الأول.

أسئلة شائعة4

ما هو التعقيد الزمني لمسألة درجات الحرارة اليومية؟

يعمل حل المكدس الرتيب بزمن O(n) ومساحة إضافية O(n). يُدفَع كل يوم إلى المكدس مرة واحدة، ويُزال منه مرة واحدة على الأكثر، لذا تُنفَّذ الحلقة الداخلية n مرات على الأكثر خلال المرور بأكمله. يستغرق الفحص إلى الأمام بدءًا من كل يوم زمنًا قدره O(n²)، أي نحو 5 × 10^7 مقارنةً لـ 10^4 يوم دون وجود يوم أدفأ.

لماذا يخزّن المكدس الفهارس بدلًا من درجات الحرارة؟

الإجابة عن يوم ما هي مسافة، today - day، لذا تحتاج إلى موضع اليوم. ويخبرك الفهرس أيضًا بأي خانة في مصفوفة الإجابات تملؤها عند إخراج اليوم من المكدس. ولا يفصلك عن درجة الحرارة سوى عملية وصول واحدة، وهي temperatures[day]، لذا فإن تخزينها أيضًا لا يضيف شيئًا.

هل يمكن حل مسألة درجات الحرارة اليومية دون استخدام مكدس؟

نعم. تحرّك من اليوم الأخير إلى اليوم الأول، وابدأ لليوم i من j = i+1. ما دام اليوم j ليس أدفأ، فانتقل إلى اليوم الذي تشير إليه إجابة j، أي j + answer[j]؛ وإذا كانت answer[j] تساوي 0، فلا يوجد يوم أدفأ، وتكون إجابة اليوم i هي 0 أيضًا. تتخطى هذه القفزات كل يوم لا يمكن أن يكون هو الإجابة، ولا يُتخطى كل يوم إلا مرة واحدة على الأكثر، ويبقى الزمن O(n) من دون استخدام ذاكرة سوى مصفوفة الإجابات.

ما العلاقة بين درجات الحرارة اليومية والعنصر الأكبر التالي؟

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

Python

def dailyTemperatures(temperatures):
    # اكتب الكود هنا

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

الحالة 1

الحالة 2

الحالة 3

المدخلات

temperatures = [71, 69, 72, 70, 70, 75, 68]

المتوقع

[2, 1, 3, 2, 1, 0, 0]