Min Stack
Alışılmış push, pop ve top işlemlerinin yanı sıra tuttuğu en küçük değeri getMin ile bildirebilen bir yığın tasarla. Dört işlemin her biri O(1) zamanda çalışmalıdır.
İşlemler sana sırasıyla ops olarak verilir; args[i], bir push için değeri, diğer tüm işlemler içinse 0 değerini içerir. İşlemleri başlangıçta boş olan tek bir yığında çalıştır ve her işlem için bir dize döndür: push ve pop için "null", top ve getMin içinse sayı metin olarak döndürülür.
Fonksiyon
- opsstring-array
- işlemler, çalıştırıldıkları sırayla
- argsinteger-array
- her push işlemi için değer, diğer tüm işlemler için 0
- Döndürürstring-array
- işlem başına bir yanıt, metin olarak
Kısıtlar
1 ≤ ops.length ≤ 3000args.length == ops.length- Her
ops[i],push,pop,topveyagetMindeğerlerinden biridir. -231+1 ≤ args[i] ≤ 231-1için push işlemi, diğer tüm işlemler içinargs[i] == 0.pop,topvegetMinyalnızca yığında en az bir değer bulunduğunda çağrılır.
Örnekler
- Girdi
- ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"]args = [4, 1, 7, 0, 0, 0, 0, 0]
- Çıktı
- ["null", "null", "null", "1", "null", "1", "null", "4"]
- Açıklama
- Yığın, alttan üste doğru 4, 1 ve 7 değerlerini tutar; bu nedenle en küçüğü 1'dir. 7'yi çıkarmak, 1'i en üstte bırakır. 1'i de çıkarmak yalnızca 4'ü bırakır, bu yüzden minimum değer yeniden 4 olur.
- Girdi
- ops = ["push", "push", "push", "getMin", "pop", "getMin", "pop", "getMin"]args = [3, -2, -2, 0, 0, 0, 0, 0]
- Çıktı
- ["null", "null", "null", "-2", "null", "-2", "null", "3"]
- Açıklama
- En küçük değer olan -2, iki kez yığına eklenir. İlk çıkarma işlemi bir kopyayı kaldırır ve diğeri hâlâ oradadır; bu nedenle
getMin-2 olarak kalır. En küçük değer ancak ikinci çıkarma işleminden sonra 3'e döner.
- Girdi
- ops = ["push", "push", "pop", "push", "getMin", "top"]args = [2, 0, 0, 8, 0, 0]
- Çıktı
- ["null", "null", "null", "null", "2", "8"]
- Açıklama
- 0 yığına eklenip tekrar çıkarılır, bu yüzden artık hesaba katılmaz. Yığında artık 2 ve 8 vardır: en üstte 8, en küçük değer ise 2’dir.
Gönderirken +16 gizli test
Ek soru
Amortize O(1) zamanda minimum değerini de bildiren, ilk giren ilk çıkar kuyruğu oluşturabilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Minimum değeri tutan tek bir değişken, o minimum değeri yığından çıkarana kadar işe yarar. O anda ne bilmeniz gerekir ve bunu ne zaman not etmiş olabilirdiniz?
Bir yığın yalnızca tepesinden değişir; bu nedenle herhangi bir yüksekliğin altındaki değerlerin en küçüğü, o yükseklik dolu kaldığı sürece aynı kalır. Eleman eklerken minimum değeri kaydedin.
Değerlerin yanında ikinci bir yığın tutun. Yeni değer tepesindeki değerden küçük veya eşit olduğunda bu yığına ekleyin ve ana yığından çıkan değer tepesindeki değere eşit olduğunda bu yığından çıkarın. Tepesi,
getMiniçin her zaman yanıttır.
Çözüm
Basit bir yığın zaten push, pop ve top işlemlerini O(1) zamanda yapar; zor olan, pop işlemlerinden sonra da geçerliliğini koruyan bir minimum bulmaktır. Temel nokta şudur: yığın yalnızca en üstünden değişir. Bir değer belirli bir yükseklikte durduğu sürece, onun altındaki hiçbir şey değişemez; bu nedenle o yüksekliğe kadarki tüm değerlerin minimumu sabittir. Push işlemi sırasında bu minimumu kaydedin; pop işlemi önceki minimumu ücretsiz olarak geri getirir. Yaklaşımlar, neyi kaydettikleri bakımından farklıdır.
Her getMin çağrısında yığını tara
Sezgi
push, pop ve top için sıradan bir yığın kullanın; getMin içinse tuttuğu her değere bakıp en küçüğünü bulun. Bu her zaman doğrudur, çünkü çağrı anındaki gerçek içeriği kontrol eder.
Ancak O(1) gereksinimini karşılamaz. n değer içeren bir yığında getMin, bu n değerin tamamını okur. Her eklemeden sonra getMin çağrısı yapan ve 1,500 değer ekleyen gizli test, yaklaşık 1,500 × 1,500 / 2, yani bir milyondan fazla değer okur; diğer yaklaşımlar ise çağrı başına bir değer okur. Bu tür 10^5 işlem çalıştıran bir sistem milyarlarca değer okur.
Önbelleğe alınmış tek bir minimum değeri bunu çözmez. En küçük değeri tutan bir değişken eklemeler için işe yarar, ancak bu değer yığından çıkarıldığında, yeniden tarama yapmadan sıradaki en küçük değerin hangisi olduğunu bilemezsiniz.
Algoritma
- Değerleri yığın olarak kullanılan bir listede sakla.
push xiçinxdeğerini ekle;popiçin son değeri kaldır;topiçin değeri oku.getMiniçin saklanan her değeri gözden geçir ve en küçüğünü döndür.- Her yanıtı metin olarak kaydet ve listeyi döndür.
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 resultMinimum değeri her değerin yanında saklayın
Sezgi
Bir değer yığının i yüksekliğinde bulunduğu sürece altındaki değerler değişemez; bu nedenle en alttaki i değerin en küçüğü, o değer orada kaldığı müddetçe sabittir. Bu sayıyı her değerin yanına kaydedin: mins adında ikinci bir yığın; burada mins[i], values[0..i] değerlerinin en küçüğüdür.
Bir push işleminde, mins yığınının yeni girdisi x ile altındaki girdiden küçük olanıdır. Bir pop işleminde, her iki yığının da en üstündeki öğeyi kaldırın; mins yığınının en üstündeki öğe yine geriye kalanların minimumudur. getMin, mins yığınının en üstündeki öğeyi okur.
İlk örnekte, 4, 1 ve 7 push işlemleri minimum değerler olarak 4, 1 ve 1'i kaydeder. 7'yi pop etmek, mins yığınının en üstünde 1'i bırakır; 1'i pop etmek ise 4'ü bırakır. Her işlem yalnızca iki yığının en üstündeki öğelere dokunur, bu nedenle her biri O(1)'dir. Bunun karşılığında her değer için ikinci bir sayı gerekir.
Algoritma
valuesveminsolmak üzere eşit yükseklikte iki yığın tut.push xiçinxdeğerinivaluesyığınının üzerine ekle vexileminsyığınının tepesindeki değerden küçük olanıminsyığınının üzerine ekle (minsboşsaxdeğerinin kendisini ekle).popiçin her iki yığından da bir öğe çıkar.topiçinvaluesyığınının tepesindeki değeri oku;getMiniçinminsyığınının tepesindeki değeri oku.- Her yanıtı metin olarak kaydet ve listeyi döndür.
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 resultYalnızca yeni bir minimum değer geldiğinde büyüyen minimumlar yığını
Sezgi
İkinci yaklaşımda mins sık sık kendini tekrar eder: önce 1'i, sonra 7, 8 ve 9'u ekleyin; mins içinde 1, 1, 1, 1 bulunur. Tekrarlanan bir kayıt size yeni bir şey söylemez. Bu yüzden mins içine yalnızca bir değer minimum olduğunda kaydedin ve aynı değer values içinden çıktığında kaldırın.
Bir ekleme işleminde, mins boşsa veya x en üstündeki değerden küçük ya da ona eşitse x'i mins içine ekleyin. Bir çıkarma işleminde, values içinden çıkan değer mins en üstündeki değere eşitse mins içinden de çıkarın. mins en üstündeki değer her zaman geçerli minimumdur: bu değerden sonra eklenen her değer ya daha büyüktür ya da ona eşit veya daha küçüktür, o da kaydedilmiştir ve o zamandan beri çıkarılmıştır.
Karşılaştırma < değil, <= olmalıdır. İkinci örnekte -2 iki kez eklenir. < ile yalnızca ilk kopya kaydedilir, ilk çıkarma işlemi onu mins içinden kaldırır ve yığında hâlâ bir -2 varken getMin 3 yanıtını verir. <= ile her kopya için ayrı bir kayıt oluşturulur.
Dört işlemin tamamı O(1) olarak kalır. Değerler en büyükten en küçüğe geldiğinde mins, values kadar büyür; minimum nadiren değiştiğinde ise kısa kalır.
Algoritma
valuesyığınını veminsyığınını tutun.push xiçinxdeğerinivaluesyığınına ekleyin.minsboşsa veyaxdeğeri en üstündeki değerden küçük ya da ona eşitse,xdeğeriniminsyığınına da ekleyin.popiçinvaluesyığınından bir değer çıkarın. Çıkarılan değerminsyığınının en üstündeki değere eşitse,minsyığınından da bir değer çıkarın.topiçinvaluesyığınının en üstündeki değeri okuyun;getMiniçinminsyığınının en üstündeki değeri okuyun.- Her yanıtı metin olarak kaydedin ve listeyi döndürün.
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
Tuzaklar ve uç durumlar
Buradaki hatalar, minimum değerin kopyalarıyla ve bir pop işleminin neyi kaldırdığıyla ilgilidir.
- Yeni bir minimumu yalnızca
xkesin olarak daha küçük olduğunda kaydetmek. Bu durumda minimum değerin ikinci kopyasıminsiçinde eksik kalır ve ilk kopya çıkarıldığında, ikincisi hâlâ yığındayken minimum kaybolur. İkinci örnek bunu yakalar. - Minimum değeri tek bir değişkende tutmak. Bu yöntem ekleme işlemlerini karşılar, ancak minimum değer çıkarıldıktan sonra değişken güncelliğini yitirir ve sıradaki en küçük değeri bulmak için tarama gerekir.
- Kutulanmış tam sayıları referanslarına göre karşılaştırmak. Java'da
Integer == Integer, ikisinin de aynı nesne olup olmadığını sorar. Java'nın önbelleğe aldığı -128 ile 127 arasındaki değerlerde bu tesadüfen doğrudur, daha büyük değerlerin çoğunda ise yanlış olur; bu nedenle pop kontrolü yalnızca büyük değerlerde bozulur. Java kodunun yaptığı gibi önceinttürüne dönüştürün. - Üçüncü yaklaşımda her pop işleminde
minsyığından bir öğe çıkarmak. Yalnızca çıkarılan değer, bu yığının en üstündeki değerse küçülür; ikinci yaklaşımda ise iki yığın her zaman birlikte hareket eder. popiçin bir sayı döndürmek. Bu biçimdepop,pushgibi"null"döndürür.
Sıkça sorulan sorular4
Bir yığındaki minimum değeri O(1) zamanda nasıl bulursunuz?
Minimum değeri ekleme anında kaydedin. Bir yığın yalnızca tepesinden değişir; bu nedenle herhangi bir yüksekliğin altındaki değerlerin minimumu, o yükseklik doluyken değişemez. Her yükseklikteki minimumu veya yalnızca her yeni minimumu tutan ikinci bir yığın kullanın; böylece getMin tepesindeki değeri okumaya dönüşür.
Değer geçerli minimuma eşit olduğunda neden min yığınına eklenir?
Minimum değer yığında birden fazla kez bulunabilir. Yalnızca kesin olarak daha küçük değerleri kaydedersen, -2'nin iki kopyası mins içinde aynı girdiyi paylaşır. -2'nin ilk kez çıkarılması bu girdiyi kaldırır ve ikinci -2 hâlâ orada olmasına rağmen getMin artık önceki minimumu bildirir. Eşit değerleri kaydetmek, her kopyanın kendine ait bir girdisi olmasını sağlar.
Min Stack, O(1) ek alanla yapılabilir mi?
Evet, bir yığın ve bir min değişkeniyle. Geçerli minimumun altına bir x eklediğinizde bunun yerine 2x - min değerini saklayın ve min = x olarak ayarlayın; saklanan sayı artık min değerinden küçüktür ve bu da onun işaretli olduğunu gösterir. İşaretli bir sayı çıkarıldığında önceki minimum 2 * min - stored olur. Aritmetik, sınır değerlere yaklaşıldığında 32 bitlik tam sayılarda taşmaya neden olur; bu nedenle 64 bitlik değerler gerekir ve işaret mantığı hataya açıktır; çoğu mülakatçı iki yığınlı sürümü tercih eder.
Min Stack'in zaman ve bellek karmaşıklığı nedir?
Her işlem O(1)'dir: push, pop, top ve getMin işlemlerinin her biri yalnızca bir veya iki yığının tepesini okur ya da değiştirir. Saklanan n değer için alan kullanımı O(n)'dir. Minimum değeri her değerin yanında saklamak her zaman 2n yuva kullanır; yalnızca yeni minimumları saklamak ise n + 1 ile 2n arasında yuva kullanır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def minStackOps(ops, args):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"] args = [4, 1, 7, 0, 0, 0, 0, 0]
Beklenen
["null", "null", "null", "1", "null", "1", "null", "4"]