Min Stack
תכנן מחסנית שבנוסף לפעולות הרגילות push, pop ו-top, יכולה לדווח על הערך הקטן ביותר שהיא מכילה באמצעות getMin. כל אחת מארבע הפעולות חייבת לפעול בזמן O(1).
הפעולות ניתנות לך לפי הסדר בתוך ops, כאשר args[i] מכיל את הערך עבור פעולת דחיפה, ו-0 עבור כל פעולה אחרת. בצע אותן על מחסנית אחת שמתחילה ריקה והחזר מחרוזת אחת לכל פעולה: "null" עבור push ו-pop, ואת המספר כטקסט עבור top ו-getMin.
פונקציה
- opsstring-array
- הפעולות, לפי סדר ביצוען
- argsinteger-array
- הערך עבור כל פעולת דחיפה, ו־0 עבור כל פעולה אחרת
- מחזירהstring-array
- תשובה אחת לכל פעולה, כטקסט
אילוצים
1 ≤ ops.length ≤ 3000args.length == ops.length- כל
ops[i]הואpush,pop,topאוgetMin. - עבור פעולת דחיפה,
-231+1 ≤ args[i] ≤ 231-1, ועבור כל פעולה אחרת,args[i] == 0. pop,topו־getMinנקראות רק כאשר המחסנית מכילה לפחות ערך אחד.
דוגמאות
- קלט
- ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"]args = [4, 1, 7, 0, 0, 0, 0, 0]
- פלט
- ["null", "null", "null", "1", "null", "1", "null", "4"]
- הסבר
- המחסנית מכילה 4, 1 ו-7 מלמטה למעלה, לכן הערך הקטן ביותר הוא 1. הוצאה של 7 משאירה את 1 בראש. הוצאה של 1 גם כן משאירה רק את 4, ולכן הערך המינימלי חוזר להיות 4.
- קלט
- ops = ["push", "push", "push", "getMin", "pop", "getMin", "pop", "getMin"]args = [3, -2, -2, 0, 0, 0, 0, 0]
- פלט
- ["null", "null", "null", "-2", "null", "-2", "null", "3"]
- הסבר
- הערך המינימלי, -2, נדחף פעמיים. השליפה הראשונה מסירה עותק אחד, והעותק השני עדיין שם, ולכן
getMinנשאר -2. רק לאחר השליפה השנייה הערך המינימלי חוזר ל־3.
- קלט
- ops = ["push", "push", "pop", "push", "getMin", "top"]args = [2, 0, 0, 8, 0, 0]
- פלט
- ["null", "null", "null", "null", "2", "8"]
- הסבר
- 0 נדחף ונשלף שוב, ולכן הוא כבר לא נחשב. המחסנית מכילה כעת את 2 ואת 8: הערך העליון הוא 8 והמינימום הוא 2.
+16 בדיקות נסתרות בשליחה
שאלת המשך
האם תוכל לבנות תור נכנס ראשון יוצא ראשון שמדווח גם על הערך המינימלי שלו בזמן O(1) בממוצע אמורטי?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
משתנה אחד שמחזיק את הערך המינימלי מספיק עד שמסירים את הערך המינימלי הזה. מה היית צריך לדעת באותו רגע, ומתי יכולת לרשום את זה?
מחסנית משתנה רק בחלק העליון שלה, ולכן הערך הקטן ביותר מבין הערכים שמתחת לכל גובה נשאר זהה כל עוד המחסנית מלאה עד לגובה הזה. רשמו את הערך המינימלי כשמוסיפים איבר למחסנית.
שמור מחסנית שנייה לצד הערכים. דחוף אליה ערך כשהערך החדש קטן או שווה לערך שבראשה, ושלוף ממנה ערך כשהערך שיוצא מהמחסנית הראשית שווה לערך שבראשה. הערך שבראשה הוא תמיד התשובה של
getMin.
פתרון
מחסנית רגילה כבר מבצעת push, pop ו־top בזמן O(1); החלק הקשה הוא לשמור על מינימום גם אחרי פעולות הוצאה מהמחסנית. העובדה המרכזית היא שמחסנית משתנה רק בקצה העליון שלה: כל עוד ערך נמצא בגובה מסוים, שום דבר מתחתיו לא יכול להשתנות, ולכן המינימום של כל הערכים עד לגובה הזה קבוע. כותבים את המינימום הזה כשמכניסים ערך למחסנית, ופעולת הוצאה מהמחסנית משחזרת בחינם את המינימום הקודם. הגישות נבדלות במה שהן כותבות.
סרוק את המחסנית בכל getMin
האינטואיציה
השתמשו במחסנית רגילה עבור push, pop ו-top, וכדי לענות על getMin עברו על כל הערכים שהיא מכילה ומצאו את הקטן ביותר. זה תמיד נכון, כי כך בודקים את התוכן בפועל ברגע הקריאה.
כך לא עומדים בדרישה של O(1). קריאה ל-getMin במחסנית שמכילה n ערכים קוראת את כל n הערכים. בדיקת ההסתרה שדוחפת 1,500 ערכים, עם קריאה ל-getMin אחרי כל דחיפה, קוראת בערך 1,500 × 1,500 / 2 — יותר ממיליון ערכים — בעוד שהגישות האחרות קוראות ערך אחד בכל קריאה. מערכת שמריצה 10^5 פעולות כאלה תקרא מיליארדי ערכים.
שמירה במטמון של המינימום בלבד לא פותרת את הבעיה. משתנה שמחזיק את הערך הקטן ביותר מתאים לדחיפות, אבל ברגע שהערך הזה נשלף, אי אפשר לדעת מהו הערך הבא הקטן ביותר בלי לעבור שוב על כל הערכים.
אלגוריתם
- שמור את הערכים ברשימה שמשמשת כמחסנית.
- עבור
push x, הוסף אתx; עבורpop, הסר את הערך האחרון; עבורtop, קרא אותו. - עבור
getMin, עבור על כל הערכים שנשמרו והחזר את הקטן ביותר. - תעד כל תשובה כטקסט והחזר את הרשימה.
class MinStack:
def __init__(self):
self.values = []
def push(self, x):
self.values.append(x)
def pop(self):
self.values.pop()
def top(self):
return self.values[-1]
def getMin(self):
# Look at every stored value: O(n).
smallest = self.values[0]
for v in self.values:
if v < smallest:
smallest = v
return smallest
def minStackOps(ops, args):
stack = MinStack()
result = []
for op, arg in zip(ops, args):
if op == "push":
stack.push(arg)
result.append("null")
elif op == "pop":
stack.pop()
result.append("null")
elif op == "top":
result.append(str(stack.top()))
else:
result.append(str(stack.getMin()))
return resultאחסן את הערך המינימלי לצד כל ערך
האינטואיציה
כל עוד ערך נמצא בגובה i של המחסנית, הערכים שמתחתיו אינם יכולים להשתנות, ולכן הערך הקטן ביותר מבין i הערכים התחתונים נשאר קבוע כל עוד הערך הזה נמצא שם. שומרים את המספר הזה לצד כל ערך: מחסנית שנייה mins שבה mins[i] הוא הערך הקטן ביותר מבין values[0..i].
בפעולת דחיפה, האיבר החדש של mins הוא הקטן מבין x והאיבר שמתחתיו. בפעולת שליפה, מסירים את האיבר העליון משתי המחסניות; האיבר העליון של mins הוא שוב הערך המינימלי מבין הערכים שנותרו. getMin קוראת את האיבר העליון של mins.
בדוגמה הראשונה, הדחיפות של 4, 1 ו-7 שומרות ערכי מינימום של 4, 1 ו-1. שליפת 7 משאירה את 1 בראש mins, ושליפת 1 משאירה את 4. כל פעולה נוגעת רק באיברים העליונים של שתי המחסניות, ולכן כל אחת מהן היא O(1). המחיר הוא מספר נוסף לכל ערך.
אלגוריתם
- שמרו על שתי מחסניות בגובה שווה,
valuesו-mins. - עבור
push x, דחפו אתxאלvalues, ודחפו אלminsאת הקטן מביןxלבין האיבר העליון שלmins(אתxעצמו אםminsריקה). - עבור
pop, שלפו איבר משתי המחסניות. - עבור
top, קראו את האיבר העליון שלvalues; עבורgetMin, קראו את האיבר העליון שלmins. - תעדו כל תשובה כטקסט והחזירו את הרשימה.
class MinStack:
def __init__(self):
self.values = []
self.mins = [] # mins[i] is the smallest of values[0..i]
def push(self, x):
self.values.append(x)
self.mins.append(x if not self.mins else min(x, self.mins[-1]))
def pop(self):
self.values.pop()
self.mins.pop()
def top(self):
return self.values[-1]
def getMin(self):
return self.mins[-1]
def minStackOps(ops, args):
stack = MinStack()
result = []
for op, arg in zip(ops, args):
if op == "push":
stack.push(arg)
result.append("null")
elif op == "pop":
stack.pop()
result.append("null")
elif op == "top":
result.append(str(stack.top()))
else:
result.append(str(stack.getMin()))
return resultמחסנית של ערכי מינימום שגדלה רק כשנוסף ערך מינימום חדש
האינטואיציה
בגישה השנייה mins חוזר על עצמו לעיתים קרובות: דוחפים 1 ואז 7, 8 ו-9, ו-mins מכיל 1, 1, 1, 1. רשומה שחוזרת על עצמה לא מוסיפה מידע חדש. לכן יש לרשום ערך ב-mins רק כשהוא הופך למינימום, ולהסיר אותו כשהערך הזה יוצא מ-values.
בעת דחיפה, מוסיפים את x ל-mins אם mins ריק או אם x קטן או שווה לערך העליון שלו. בעת שליפה, אם הערך שיוצא מ-values שווה לערך העליון של mins, שולפים גם מ-mins. הערך העליון של mins הוא תמיד המינימום הנוכחי: כל ערך שנדחף אחריו גדול יותר, או שהיה קטן או שווה לו, נרשם גם הוא, ונשלף מאז.
ההשוואה חייבת להיות <=, ולא <. בדוגמה השנייה, -2 נדחף פעמיים. עם < רק העותק הראשון נרשם, השליפה הראשונה מסירה אותו מ-mins, ואז getMin מחזירה 3 בזמן ש--2 עדיין נמצא במחסנית. עם <= לכל עותק יש רשומה משלו.
כל ארבע הפעולות נשארות O(1). כשהערכים מגיעים מהגדול לקטן, mins גדל עד לגובה של values; כשהמינימום משתנה לעיתים רחוקות, הוא נשאר קצר.
אלגוריתם
- החזק מחסנית
valuesומחסניתmins. - עבור
push x, דחוף אתxאלvalues. אםminsריקה או ש-xקטן או שווה לאיבר שבראשה, דחוף גם אתxאלmins. - עבור
pop, שלוף איבר מ-values. אם הערך שהוסר שווה לאיבר שבראשmins, שלוף גם איבר מ-mins. - עבור
top, קרא את האיבר שבראשvalues; עבורgetMin, קרא את האיבר שבראשmins. - תעד כל תשובה כטקסט והחזר את הרשימה.
class MinStack:
def __init__(self):
self.values = []
self.mins = [] # each value that was a minimum when pushed; the top is the current minimum
def push(self, x):
self.values.append(x)
# <= keeps one copy per equal minimum, so popping one leaves the others.
if not self.mins or x <= self.mins[-1]:
self.mins.append(x)
def pop(self):
if self.values.pop() == self.mins[-1]:
self.mins.pop()
def top(self):
return self.values[-1]
def getMin(self):
return self.mins[-1]
def minStackOps(ops, args):
stack = MinStack()
result = []
for op, arg in zip(ops, args):
if op == "push":
stack.push(arg)
result.append("null")
elif op == "pop":
stack.pop()
result.append("null")
elif op == "top":
result.append(str(stack.top()))
else:
result.append(str(stack.getMin()))
return result
מלכודות ומקרי קצה
השגיאות כאן נוגעות לעותקים של הערך המינימלי ולמה שפעולת הוצאה מהמחסנית מסירה.
- רישום ערך מינימלי חדש רק כאשר
xקטן ממנו ממש. כך חסר עותק שני של הערך המינימלי ב־mins, והוצאת העותק הראשון מסירה את הערך המינימלי, אף שהעותק השני עדיין נמצא במחסנית. הדוגמה השנייה חושפת זאת. - שמירת הערך המינימלי במשתנה אחד. זה עובד בהוספות למחסנית, אבל לאחר שמוציאים את הערך המינימלי המשתנה מכיל ערך מיושן, וכדי למצוא את הערך הבא בגודלו צריך לסרוק.
- השוואת מספרים שלמים עטופים לפי הפניה. ב־Java,
Integer == Integerבודק אם שניהם אותו אובייקט. במקרה זה, הדבר נכון לערכים מ־-128 עד 127, ש־Java שומרת במטמון, ונכשל ברוב הערכים הגדולים יותר, ולכן בדיקת ההוצאה מהמחסנית נכשלת רק בערכים גדולים. יש להסיר את העיטוף ולהמיר תחילה ל־int, כפי שעושה קוד ה־Java. - הוצאת איבר מ־
minsבכל פעולת הוצאה מהמחסנית בגישה השלישית. גודל המחסנית הזו קטן רק כשהערך שהוסר הוא האיבר העליון שלה; בגישה השנייה שתי המחסניות תמיד משתנות יחד. - החזרת מספר עבור
pop. בפורמט הזהpopמחזירה"null", כמוpush.
שאלות נפוצות4
איך מוצאים את הערך המינימלי במחסנית בזמן O(1)?
רשום את הערך המינימלי בזמן ההכנסה למחסנית. מחסנית משתנה רק בקודקוד שלה, ולכן הערך המינימלי של הערכים שמתחת לכל גובה אינו יכול להשתנות כל עוד הגובה הזה תפוס. החזק מחסנית שנייה עם הערך המינימלי בכל גובה, או רק עם כל ערך מינימלי חדש, ו־getMin הופכת לקריאה של הקודקוד שלה.
למה לדחוף למחסנית המינימום כשהערך שווה למינימום הנוכחי?
מפני שהערך המינימלי יכול להופיע במחסנית יותר מפעם אחת. אם מתעדים רק ערכים קטנים יותר ממש, שני עותקים של -2 חולקים רשומה אחת ב־mins. השליפה הראשונה של -2 מסירה את הרשומה הזאת, ואז getMin מחזירה את הערך המינימלי הקודם, אף שהעותק השני של -2 עדיין נמצא שם. תיעוד של ערכים שווים נותן לכל עותק רשומה משלו.
האם אפשר לממש מחסנית מינימום עם O(1) מקום נוסף?
כן, עם מחסנית אחת ומשתנה אחד min. כשדוחפים x מתחת למינימום הנוכחי, שומרים במקום זאת את 2x - min ומגדירים min = x; המספר שנשמר קטן כעת מ־min, וזה הסימן שלו. כשמוציאים מספר מסומן, המינימום הקודם הוא 2 * min - stored. החשבון חורג מטווח המספרים השלמים בני 32 סיביות בקרבת הגבולות, ולכן נדרשים ערכים בני 64 סיביות, והלוגיקה של הסימן מועדת לשגיאות; רוב המראיינים מסתפקים בגרסה עם שתי מחסניות.
מהי סיבוכיות הזמן והמקום של מחסנית מינימום?
כל פעולה היא O(1): הפעולות push, pop, top ו-getMin קוראות או משנות רק את החלק העליון של מחסנית אחת או שתיים. צריכת המקום היא O(n) עבור n ערכים מאוחסנים. אחסון המינימום לצד כל ערך משתמש תמיד ב-2n מקומות; אחסון מינימום חדשים בלבד משתמש בין n + 1 ל-2n מקומות.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def minStackOps(ops, args):
# כתבו כאן את הקודמקרה 1
מקרה 2
מקרה 3
קלט
ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"] args = [4, 1, 7, 0, 0, 0, 0, 0]
צפוי
["null", "null", "null", "1", "null", "1", "null", "4"]