Min Stack
صمّم مكدّسًا يمكنه، بالإضافة إلى العمليات المعتادة push وpop وtop، الإبلاغ عن أصغر قيمة يحتوي عليها باستخدام getMin. يجب أن تُنفَّذ كل واحدة من العمليات الأربع في زمن O(1).
تُعطى لك العمليات بالترتيب ضمن ops، وتحتوي args[i] على القيمة لعملية push وعلى 0 لكل عملية أخرى. نفّذها على مكدّس واحد يبدأ فارغًا، وأعِد سلسلة نصية واحدة لكل عملية: "null" لعمليتي push وpop، والعدد كنص لعمليتي top وgetMin.
الدالة
- opsstring-array
- العمليات، حسب ترتيب تنفيذها
- argsinteger-array
- القيمة لكل عملية push، و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 من القيم يقرأها جميعًا. يقرأ الاختبار المخفي الذي يضيف 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].
عند إجراء push، تكون قيمة الإدخال الجديدة في mins هي الأصغر بين x والقيمة التي تحتها. وعند إجراء pop، أزل العنصر العلوي من كلا المكدسين؛ فيكون أعلى mins مجددًا هو أصغر ما تبقى. تقرأ getMin أعلى mins.
في المثال الأول، تخزّن عمليات push للقيم 4 و1 و7 القيم الدنيا 4 و1 و1. إزالة 7 تُبقي 1 في أعلى mins، وإزالة 1 تُبقي 4. تلامس كل عملية أعلى مكدسين فقط، لذا يستغرق كل منها O(1). والثمن هو تخزين عدد ثانٍ لكل قيمة.
الخوارزمية
- حافظ على مكدسين متساويين في الارتفاع،
valuesوmins. - عند تنفيذ
push x، ادفعxإلىvalues، وادفع الأصغر بينxوقمةminsإلى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"]