Daily Temperatures

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

פתרון המחסנית המונוטונית פועל בזמן 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, ולכן ההמתנה היא 2 ימים. הטמפרטורות בימים 3 ו־4 הן שתיהן 70: הטמפרטורה ביום 4 אינה חמה יותר, ולכן ביום 3 ממתינים עד יום 5, שבו הטמפרטורה היא 75 — כלומר 2 ימים. אחרי 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 השני אינו מוציא את הראשון מהמחסנית, כי שוויון אינו נחשב לחם יותר. יום 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

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

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

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

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