Stock Span Problem
מקבלים את מחיר הסגירה של מניה בכל יום: prices[i] הוא המחיר ביום i. הטווח של יום i הוא מספר הימים הרצופים, המסתיימים ביום i וכוללים אותו, שבהם המחיר היה קטן או שווה ל-prices[i].
החזירו את הטווח של כל יום, באותו סדר כמו prices. כל טווח הוא לפחות 1, כי יום תמיד נחשב לעצמו.
פונקציה
- pricesinteger-array
- המחיר בכל יום, לפי הסדר
- מחזירהinteger-array
- הטווח של כל יום, באותו סדר
אילוצים
1 ≤ prices.length ≤ 1041 ≤ prices[i] ≤ 105- יום מוקדם יותר עם אותו מחיר נחשב כחלק מהטווח; רק מחיר גבוה יותר ממש עוצר אותו.
דוגמאות
- קלט
- prices = [31, 27, 14, 21, 30, 18, 40]
- פלט
- [1, 1, 1, 2, 4, 1, 7]
- הסבר
- ביום 3, ב־21, חוזרים אחורה מעבר ל־14 ועוצרים ב־27: טווח 2. ביום 4, ב־30, עוצרים ב־31: טווח 4. ביום 6, ב־40, עולים על כל המחירים הקודמים ומכסים את כל 7 הימים.
- קלט
- prices = [8, 8, 3, 8]
- פלט
- [1, 2, 1, 4]
- הסבר
- גם מחירים שווים נחשבים, לכן היום 1 במחיר 8 מכסה את היום 0 ומקבל 2. היום 3 במחיר 8 מכסה את היום 3 ואת שני הימים הקודמים שמחירם 8, כלומר טווח של 4.
- קלט
- prices = [50, 40, 30, 20]
- פלט
- [1, 1, 1, 1]
- הסבר
- כל יום זול יותר מהיום שלפניו, לכן אף טווח אינו מגיע לאחור מעבר ליום עצמו, וכל טווח הוא 1.
שאלת המשך
כעת המחירים מגיעים בזה אחר זה, ועליך לדווח על כל טווח כשהמחיר מגיע. איזו גישה עדיין עובדת, ומה היא שומרת בין קריאות?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
ספירה לאחור מכל יום חוזרת על אותה עבודה: אחרי 8000 ימים באותו מחיר, היום האחרון לבדו חוזר 8000 ימים לאחור. כשחוזרים לאחור מהיום, על אילו ימים קודמים אפשר לדלג לצמיתות?
ברגע שמחיר היום גבוה לפחות כמו מחירו של יום מוקדם יותר כלשהו, אותו יום מוקדם יותר כבר לא יכול להיות היום שעוצר רצף מאוחר יותר: היום קרוב יותר ויקר לפחות באותה מידה. רק הימים שיקרים יותר מכל הימים שבאים אחריהם עדיין חשובים, ומחיריהם יורדים מהישן ביותר לחדש ביותר.
עבור על הימים לפי הסדר ושמור במחסנית, כאינדקסים, את הימים הקודמים שעדיין חשובים. לפני שתענה לגבי היום הנוכחי, הוצא מהמחסנית כל יום שמחירו קטן או שווה למחיר של היום הנוכחי. מחסנית ריקה פירושה שהטווח מגיע עד יום 0; אחרת, הוא נעצר יום אחד אחרי היום שנותר בראש המחסנית. לאחר מכן דחוף את היום הנוכחי למחסנית.
פתרון
הטווח של יום מסתיים ביום הקודם הקרוב ביותר שבו המחיר גבוה יותר באופן strict. חזרה לאחור כדי למצוא אותו עולה עד n צעדים לכל יום. במקום זאת, נשמור רק את הימים שעדיין יכולים לעצור טווח עתידי: מחסנית של אינדקסים עם מחירים שהולכים ויורדים באופן strict מוצאת את כל הגבולות במעבר אחד.
ספור לאחור מכל יום
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
פעל לפי ההגדרה. ביום i, צעד אחורה יום אחד בכל פעם כל עוד המחיר באותו יום קטן או שווה ל-prices[i], וספור גם את יום i. המחיר הראשון שגבוה ממנו ממש, או תחילת המערך, מסיים את הרצף.
אף צעד לא משתמש מחדש בצעד קודם. במחירים קבועים או עולים, כל הליכה חוזרת עד יום 0: n = 10^4 ימים פירושם כ-5 × 10^7 צעדים.
אלגוריתם
- צרו את
span, מערך שאורכו כאורךprices. - עבור כל יום
i, הגדירו מונה ל-0 ומצביעjל-i. - כל עוד
j ≥ 0ו-prices[j] ≤ prices[i], הוסיפו 1 למונה והזיזו אתjיום אחד לאחור. - שמרו את המונה ב-
span[i]. אחרי היום האחרון, החזירו אתspan.
def stockSpan(prices):
span = []
for i in range(len(prices)):
count = 0
j = i
# Count today and every earlier day in a row that is not more expensive.
while j >= 0 and prices[j] <= prices[i]:
count += 1
j -= 1
span.append(count)
return spanמחסנית מונוטונית של ימים גבוהים יותר
האינטואיציה
נקרא ליום המוקדם הקרוב ביותר שבו המחיר גבוה ממש בשם החוסם. הטווח הוא today - blocker, או today + 1 כשאין כזה.
בדוגמה הראשונה, מחירו של יום 3 הוא 21 ומחירו של יום 4 הוא 30. כל הליכה מאוחרת יותר מגיעה תחילה ליום 4, וכל מחיר שעובר את 30 עובר גם את 21, ולכן יום 3 לעולם לא יוכל שוב לחסום. באופן כללי, כשמגיע היום הנוכחי, כל מועמד מוקדם יותר שמחירו קטן או שווה למחיר של היום הנוכחי כבר אינו רלוונטי: מוציאים אותו מהמחסנית. היום שנותר בראש המחסנית הוא החוסם של היום הנוכחי. לאחר מכן דוחפים את היום הנוכחי.
מחירי האיברים במחסנית יורדים ממש מלמטה למעלה, ולכן האיבר הראשון שנותר הוא המחיר הגבוה הקרוב ביותר. בדוגמה הראשונה, יום 4 מוציא מהמחסנית את ימים 3 ו-1 ועוצר ביום 0, לטווח של 4 - 0 = 4. כל יום נדחף פעם אחת ומוצא מהמחסנית לכל היותר פעם אחת, ולכן המעבר פועל בזמן O(n).
אלגוריתם
- צרו את מערך
spanומחסנית ריקה לאינדקסים של ימים. - עבור כל יום
today, הוציאו מהמחסנית אינדקסים כל עוד המחיר שלהם קטן או שווה ל-prices[today]. - אם המחסנית ריקה, הטווח הוא
today + 1; אחרת הואtodayפחות האינדקס שבראש המחסנית. - דחפו את
todayועברו ליום הבא. החזירו אתspan.
def stockSpan(prices):
span = [0] * len(prices)
higher = [] # indices of earlier days, prices strictly falling toward the top
for today, price in enumerate(prices):
# A day that is not more expensive than today can never stop a later span.
while higher and prices[higher[-1]] <= price:
higher.pop()
# The span reaches back to the nearest more expensive day, or to day 0.
span[today] = today - higher[-1] if higher else today + 1
higher.append(today)
return span
מלכודות ומקרי קצה
- ביצוע הוצאה מהמחסנית כשמגיעים ל־
<במקום ל־<=. ב־[8, 8, 3, 8]הטווח של היום האחרון הוא 4; עצירה ב־8 המוקדם יותר נותנת 2. - כתיבת
todayבמקוםtoday + 1כשהמחסנית ריקה. יום 0 חייב לקבל 1, לא 0. - ביצוע הוצאה מהמחסנית פעם אחת בלבד בכל יום. בדוגמה הראשונה, 40 צריך להסיר את הימים 5, 4 ו־0. עצירה אחרי יום 5 גורמת ליום 4 להיראות כמו החסם שלו, ונותנת טווח של 2 במקום 7.
- ב־Lua וב־R, המערכים מתחילים ב־1. באינדקסים שמתחילים ב־1, הטווח כשהמחסנית ריקה הוא
today, לאtoday + 1.
שאלות נפוצות4
מהי סיבוכיות הזמן של בעיית טווח המניות?
זמן של O(n) ומקום נוסף של O(n) באמצעות מחסנית מונוטונית, מכיוון שכל יום יוצא מהמחסנית לכל היותר פעם אחת. מעבר לאחור מכל יום הוא O(n²) כשהמחירים ממשיכים לעלות או נשארים ללא שינוי.
האם המחסנית צריכה לאחסן מחירים או אינדקסים של ימים?
אינדקסים של ימים. הטווח הוא ספירה של ימים, ורק האינדקס של החוסם נותן לך את זה. prices[index] מחזיר את המחיר לצורך ההשוואה.
האם אפשר לפתור את בעיית טווח המניות בלי מחסנית נפרדת?
כן. מתחילים ב-j = today - 1; כל עוד j ≥ 0 וגם prices[j] ≤ prices[today], קופצים אל j - span[j], מכיוון שהמחיר בכל יום בתוך הטווח הזה הוא לכל היותר prices[j]. אורך הטווח הוא today - j. הקפיצות נוחתות רק בימים שהמחסנית הייתה מחזיקה, ולכן המעבר נשאר O(n).
האם בעיית טווח המניות היא בעיית האיבר הגדול הקודם?
כן, המדידה היא בימים: עבור כל יום, מוצאים את היום המוקדם ביותר הקרוב ביותר שבו המחיר גבוה יותר באופן ממש, ומדווחים כמה ימים אחורה הוא נמצא. הופכים את כיוון הסריקה או את ההשוואה, ואותה מחסנית נותנת את הערך הבא הגדול יותר, הבא הקטן יותר או הקודם הקטן יותר.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def stockSpan(prices):
# כתבו כאן את הקודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנט
prices = [31, 27, 14, 21, 30, 18, 40]
הפלט הצפוי
[1, 1, 1, 2, 4, 1, 7]