Daily Temperatures

Q: מהי סיבוכיות הזמן של Daily Temperatures?

פתרון המחסנית המונוטונית פועל בזמן O(n) ומשתמש ב- O(n) מקום נוסף, כי כל יום נדחף פעם אחת ונשלף לכל היותר פעם אחת. סריקה קדימה מכל יום אורכת זמן של O(n²) , כלומר כ-5 × 10^7 השוואות עבור 10^4 ימים ללא יום חם יותר.

Q: האם אפשר לפתור את אתגר הטמפרטורות היומיות בלי מחסנית?

כן. מלאו את התשובות מהיום האחרון לאחור, ועבור יום i התחילו ב- j = i+1 ; כל עוד יום j אינו חם יותר, דלגו אל j + answer[j] , היום שעונה על j . אם answer[j] הוא 0, גם התשובה של יום i תהיה 0. הדילוגים מדלגים על ימים שאינם יכולים לענות עבור i : זמן 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) ממתין יומיים ל־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

מהי סיבוכיות הזמן של Daily Temperatures?

פתרון המחסנית המונוטונית פועל בזמן 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), ללא זיכרון נוסף.

מה הקשר בין Daily Temperatures ל-Next Greater Element?

זו אותה שאלה שנשאלת עבור כל מיקום: מצא את הערך הבא הגדול יותר מימין. 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]