Daily Temperatures

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

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

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

+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) يومين حتى اليوم 72. يتجاوز اليوم 3 (70) القيمة 70 المساوية في اليوم 4، وينتظر يومين حتى 75. لا توجد درجة حرارة أعلى بعد 75 أو 68، لذا تكون النتيجة 0 لكليهما.

سؤال إضافي

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

الحل

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

امسح إلى الأمام انطلاقًا من كل يوم

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

الفكرة

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

إذا كانت درجات الحرارة في جميع الأيام البالغ عددها 10^4 متساوية، فلن يتوقف أي فحص مبكرًا: نحو 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. ثم أضف اليوم الحالي إلى المكدّس.

لا تحتاج إلا إلى التحقق من العنصر الأعلى. لا يُضاف يوم إلى المكدّس إلا بعد إزالة كل الأيام الأبرد منه الموجودة فوقه، لذا لا ترتفع درجات الحرارة في المكدّس من الأسفل إلى الأعلى. إذا لم يكن اليوم الحالي أدفأ من العنصر الأعلى، فلن يكون أدفأ من أي عنصر تحته، فتتوقف عن الإزالة. في المثال الأول، يزيل اليوم 5 (75) الأيام 4 و3 و2، بفترات انتظار 1 و2 و3، بينما لم تتمكن درجة الحرارة 70 الثانية من إزالة اليوم الأول، لأن تساوي الحرارة لا يعني أنها أدفأ.

يُضاف كل يوم مرة واحدة، وتتم إزالته مرة واحدة على الأكثر، لذا لا يتجاوز مجموع عمليات الإزالة 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

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

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

أسئلة شائعة3

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

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

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

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

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

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

def dailyTemperatures(temperatures):
    # اكتب الشيفرة هنا

اختبار #1

اختبار #2

اختبار #3

وسيط

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

الإخراج المتوقع

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