Tekdüze Yığın Kalıbı
Günlük sıcaklıklar, histogramdaki en büyük dikdörtgen ve sonraki daha büyük öğe problemlerini O(n) sürede çözmek için tekdüze yığını uygulayın.
Tekdüze Yığın Kalıbı, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 3. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.
Monotonik Yığın Nedir?
Monotonik yığın, öğeleri arasında sıralı bir değişmez koşulu koruyan bir yığındır. Artan monotonik yığın öğeleri alttan üste doğru artar; azalan monotonik yığın öğeleri alttan üste doğru azalır. Yeni bir öğe bu koşulu bozduğunda, koşul yeniden sağlanana kadar öğeler çıkarılır ve ardından yeni öğe yığına eklenir.
Bu basit mekanizma, doğrudan iç içe O(n²) döngüler gerektirecek 'en yakın daha büyük öğe' ve 'en yakın daha küçük öğe' sorgularını O(n) zamanda yanıtlamayı sağlar.
# Build a monotonically increasing stack from [3,1,2,5,4]
nums = [3, 1, 2, 5, 4]
stack = []
for n in nums:
while stack and stack[-1] > n:
stack.pop() # remove elements that violate increasing order
stack.append(n)
print('stack:', stack)Bir Sonraki Daha Büyük Öğe (LeetCode 496)
Her öğe için sağında bulunan ve ondan kesinlikle büyük olan ilk öğeyi bulun. Kaba kuvvetli O(n²) yaklaşımı, her konumdan başlayarak sağa doğru tarama yapar. Monotonik yığın yaklaşımında indekslerden oluşan azalan bir yığın tutulur. Daha büyük bir öğeyle karşılaşıldığında, daha küçük öğelere ait tüm indeksleri çıkarın; onların 'bir sonraki daha büyük öğesi' geçerli öğedir. Yığında kalan indekslerin bir sonraki daha büyük öğesi yoktur; bu nedenle yanıtları -1 olur.
def nextGreaterElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, decreasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] < val:
j = stack.pop()
result[j] = val
stack.append(i)
return result
print(nextGreaterElement([2, 1, 2, 4, 3])) # [4, 2, 4, -1, -1]
print(nextGreaterElement([1, 3, 2, 4])) # [3, 4, 4, -1]Dairesel Dizide Bir Sonraki Daha Büyük Öğe
LeetCode 503 'Bir Sonraki Daha Büyük Öğe II': Aynı problem, ancak dizi dairesel kabul edilir. Dizinin sonuna ulaştıktan sonra başa dönüp başlangıçtan itibaren kontrol edin. İpucu şudur: dizi üzerinde iki kez dolaşın (0'dan 2n-1'e kadar indeksler) ve özgün diziyi indekslemek için i % n kullanın. Yinelenen işlemeyi önlemek için yalnızca [0, n-1] aralığındaki indeksleri yığına ekleyin.
def nextGreaterElements(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
j = stack.pop()
result[j] = nums[i % n]
if i < n:
stack.append(i)
return result
print(nextGreaterElements([1, 2, 1])) # [2, -1, 2]
print(nextGreaterElements([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]Günlük Sıcaklıklar: Tam Çözüm
LeetCode 739'a dönüş: her gün için daha sıcak bir sıcaklığa kaç gün kaldığını bulun. Monotonik yığın, sıcaklıkları azalan sırada olan günlerin indekslerini tutar. Daha sıcak bir gün olan i bulunduğunda, yığındaki daha soğuk gün indekslerinin tümünü çıkarın ve result[j] = i - j değerini kaydedin. Yığında kalan günler hiçbir zaman daha sıcak bir gün bulamadığından, sonuçları 0 olarak kalır.
def dailyTemperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices, decreasing temperatures
for i, t in enumerate(temperatures):
while stack and temperatures[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(dailyTemperatures(temps))
# [1, 1, 4, 2, 1, 1, 0, 0]Önceki Daha Küçük Öğe
'Önceki daha küçük öğe' sorgusu şunu sorar: her öğe için solundaki en yakın daha küçük değer nedir? Soldan sağa ilerlerken artan bir monotonik yığın kullanın. i indeksini yığına eklemeden önce yığının tepesindeki öğe, önceki daha küçük öğedir; çünkü nums[i] değerinden büyük tüm öğeler, onları çıkarmaya zorlayan önceki eklemeler sırasında zaten çıkarılmıştır.
def previousSmallerElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, increasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] >= val:
stack.pop()
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
print(previousSmallerElement([4, 5, 2, 10, 8])) # [-1, 4, -1, 2, 2]
print(previousSmallerElement([3, 1, 2])) # [-1, -1, 1]Histogramdaki En Büyük Dikdörtgen
LeetCode 84 'Histogramdaki En Büyük Dikdörtgen': indekslerden oluşan monotonik artan bir yığın kullanılır. Her çubuk için, geçerli çubuktan daha yüksek olan tüm çubukları çıkarın. Çıkarılan her h çubuğu için sağ sınır geçerli i indeksidir; sol sınır ise yeni yığın tepesinin 1 fazlasıdır (yığın boşsa 0). Alan = h × (sağ - sol). Sonda kalan tüm çubukların çıkarılmasını zorlamak için yüksekliği 0 olan bir nöbetçi öğeyi sona ekleyin.
def largestRectangleArea(heights):
heights = heights + [0] # sentinel
stack = [] # indices, increasing heights
result = 0
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
left = stack[-1] + 1 if stack else 0
width = i - left
result = max(result, height * width)
stack.append(i)
return result
print(largestRectangleArea([2, 1, 5, 6, 2, 3])) # 10
print(largestRectangleArea([2, 4])) # 4
print(largestRectangleArea([1])) # 1Maksimum Dikdörtgen (LeetCode 85)
LeetCode 85 'Maksimum Dikdörtgen', histogram problemini 2B ikili matrise genişletir. Her satır için birikimli çubuk yüksekliklerini hesaplayın: matrix[row][col] == '1' ise yükseklik, bu hücreyi ve üstündeki ardışık 1'lerin sayısıdır. Ardından her satırın yükseklikler dizisine 'histogramdaki en büyük dikdörtgen' algoritmasını uygulayın. m×n boyutundaki bir matris için zaman karmaşıklığı O(m × n)'dir.
def maximalRectangle(matrix):
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
result = 0
def largest_in_hist(h):
h = h + [0]
stack, best = [], 0
for i, val in enumerate(h):
while stack and h[stack[-1]] > val:
height = h[stack.pop()]
left = stack[-1] + 1 if stack else 0
best = max(best, height * (i - left))
stack.append(i)
return best
for row in matrix:
for j, cell in enumerate(row):
heights[j] = heights[j] + 1 if cell == '1' else 0
result = max(result, largest_in_hist(heights[:]))
return result
m = [['1','0','1','0','0'],['1','0','1','1','1'],
['1','1','1','1','1'],['1','0','0','1','0']]
print(maximalRectangle(m)) # 6Yağmur Suyu Biriktirme: Yığın Yaklaşımı
LeetCode 42 'Yağmur Suyu Biriktirme' probleminde yığın kullanın: indekslerden oluşan azalan bir yığın tutun. Daha yüksek bir çubukla karşılaşıldığında bir çukur oluşur. Çukurun tabanını çıkarın; su genişliğini (geçerli indeks - yığın tepesi - 1), yüksekliğini ise (minimum(geçerli çubuk, yeni yığın tepesindeki çubuk) - çukur yüksekliği) olarak hesaplayın. Tüm katkıları toplayın. Zaman: O(n), bellek: O(n).
def trap(height):
stack = []
water = 0
for i, h in enumerate(height):
while stack and height[stack[-1]] < h:
bottom = stack.pop()
if not stack:
break
left = stack[-1]
width = i - left - 1
bounded_h = min(h, height[left]) - height[bottom]
water += width * bounded_h
stack.append(i)
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap([4,2,0,3,2,5])) # 9Monotonik Yığın Problemlerini Tanıma
Monotonik yığının doğru araç olduğunu gösteren işaretler şunlardır: problem bir sonraki veya önceki daha büyük/küçük öğeyi sorar, her öğenin yanıtı belirli bir yöndeki öğelere bağlıdır ya da basit O(n²) çözümünde her öğe için sola veya sağa tarama yapılır. Yığın, gelecekteki öğeler için yanıt olabilecek adayları saklar ve daha iyi bir aday gelir gelmez daha kötü adayları eler.
En başta şu kararı mutlaka verin: artan yığın mı (sonraki/önceki daha küçük öğe için) yoksa azalan yığın mı (sonraki/önceki daha büyük öğe için) kullanacaksınız ve hangi yönde ilerleyeceksiniz?
Amortismanlı O(n) Analizi
Monotonik yığın algoritmaları, iç döngünün dış döngü içinde yer alması nedeniyle ilk bakışta O(n log n) veya O(n²) gibi görünebilir. Ancak her öğe en fazla bir kez yığına eklenir ve en fazla bir kez çıkarılır. Toplam ekleme işlemi sayısı n'dir ve toplam çıkarma işlemi sayısı da en fazla n'dir. Bu nedenle tüm yinelemeler boyunca toplam iş 2n işlemdir; O(n²) değil, amortismanlı olarak O(n)'dir.
# Count total pushes and pops for n=1000
n = 1000
nums = list(range(n, 0, -1)) # worst case for decreasing stack
stack = []
pushes = pops = 0
for val in nums:
while stack and stack[-1] < val:
stack.pop()
pops += 1
stack.append(val)
pushes += 1
print(f'n={n}, pushes={pushes}, pops={pops}, total={pushes+pops}')
# Total <= 2*nÖzet: Monotonik Yığın Değişmez Koşulu Seçimleri
Yığın yönünü sorguya göre seçin. Bir sonraki daha büyük öğe için azalan yığın kullanın; geçerli öğe daha büyük olduğunda öğeleri çıkarın. Bir sonraki daha küçük öğe için artan yığın kullanın; geçerli öğe daha küçük olduğunda öğeleri çıkarın. En büyük dikdörtgen için artan yığın kullanın ve daha kısa bir çubuk göründüğünde öğeleri çıkarın. Kayan pencere maksimumu için azalan çift uçlu kuyruk kullanın ve her iki uçtan da öğe çıkarın.
Kodlamadan önce değişmez koşulu bir yorumda yazmak, mantığı netleştirir ve hata ayıklamayı hızlandırır.
Hızlı Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını ne kadar anladığınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: monotonik yığın, yeni öğeyi eklemeden önce değişmez koşulu bozan öğeleri çıkararak sıralı bir değişmez koşulu korur, azalan yığınlar bir sonraki daha büyük öğe sorgularını, artan yığınlar ise bir sonraki daha küçük öğe sorgularını yanıtlar ve her öğe en fazla bir kez eklenip çıkarıldığı için toplam süre amortismanlı olarak O(n)'dir. Sırada yığınları kullanarak kuyrukları ve kuyrukları kullanarak yığınları uygulayacağız.
Sıkça Sorulan Sorular
“Tekdüze Yığın Kalıbı” dersi ücretsiz mi?
Evet — “Tekdüze Yığın Kalıbı” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.
“Tekdüze Yığın Kalıbı” dersinde ne öğreneceğim?
Günlük sıcaklıklar, histogramdaki en büyük dikdörtgen ve sonraki daha büyük öğe problemlerini O(n) sürede çözmek için tekdüze yığını uygulayın. DSA Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te DSA Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 3. dersidir.
“Tekdüze Yığın Kalıbı” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her DSA Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Yığın Uygulaması ve Kullanım Alanları
- Kuyruk Uygulaması ve Çift Uçlu Kuyruk
- Tekdüze Yığın Kalıbı
- Yığın ve Kuyruğun Birbirini Simüle Etmesi