Sabit zamanlı min stack
Görev tanımı
Problem
Bir değer push etmeyi, tepedeki değeri pop etmeyi, tepedeki değeri okumayı ve o an saklanan en küçük değeri bildirmeyi destekleyen bir stack tasarla. Bu işlemlerin her biri sabit zamanda çalışmalı; yani minimumu bulmak için içeriği taramak kabul edilmez. Minimumun yalnız stack boş değilken istendiğini varsayabilirsin.
Örnekler
Operations: push 5, push 2, push 7
minimum -> 2, top -> 7
Operations: pop, pop (starting from the stack above)
minimum -> 5, top -> 5
Neden: 2'yi pop etmek önceki minimumu geri getirmeli
Operations: push 3, push 3, pop
minimum -> 3
Neden: edge case: tekrar eden minimumlar bir pop'tan sağ çıkmalı
İpuçları
0 / 3
Minimumu tutan tek bir sayı, o minimum pop edildiği anda bozulur, çünkü önceki minimum gitmiştir. Geçmişin bir şekilde tutulması gerekir.
Minimumun yalnız push ve pop anlarında değiştiğine ve tam olarak stack'in kendisine uyan son giren ilk çıkar biçiminde değiştiğine dikkat et.
Değerlerin yanında, tepesi her zaman eşleşen seviyenin altındaki her şeyin minimumunu tutan paralel bir stack tut. Push'ta yeni değer ile mevcut minimumun küçüğünü sakla. Pop'ta iki stack'in tepesini birlikte at.
- Hedef zaman
- O(1)
- Hedef alan
- O(n)
Kısıtlar
- every operation runs in O(1) time
- minimum is only requested on a non-empty stack
Çözüm
İkinci bir stack ana stack'i yansıtır ve her seviyede o seviyedeki ve altındaki her şeyin minimumunu saklar. Push etmek gelen değer ile önceki minimumun küçüğünü kaydeder, bu yüzden yansıtmanın tepesi her zaman cevaptır. Pop etmek iki tepeyi birlikte atar; bu, önceki minimumu kendiliğinden geri getirir ve tekrar eden minimumları doğru ele alır. Her işlem O(1) zaman, ek stack için alan O(n).
class MinStack:
def __init__(self): self.items, self.mins = [], [] # mins mirrors the running minimum
def push(self, x):
self.items.append(x)
# each level remembers the minimum of everything at or below it
self.mins.append(x if not self.mins else min(x, self.mins[-1]))
def pop(self):
self.mins.pop() # both stacks always shrink together
return self.items.pop()
def top(self): return self.items[-1]
def minimum(self): return self.mins[-1]
s = MinStack()
for v in (5, 2, 7): s.push(v)
print(s.minimum(), s.top()) # -> 2 7
s.pop(); s.pop()
print(s.minimum(), s.top()) # -> 5 5Kodda değil de fikirde mi takıldın? Min stack bunu anlatıyor.