Deque ile Kayan Pencere Maksimumu
Pencerenin uç değerlerini O(n) içinde koruyun.
Deque ile Kayan Pencere Maksimumu, CoddyKit'te ücretsiz bir Competitive Programming Academy dersidir. Bu, 4 dersinin 4. 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, Competitive Programming Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Competitive Programming Academy kursu toplamda 4 dersten oluşur.
Kayan Pencerenin Maksimumu
Bir dizi ve k pencere boyutu verildiğinde, pencere sağa kayarken her pencerenin maksimumunu bulmak istersiniz. Bunu naif biçimde yapmak O(n çarpı k) sürer.
Daha Hızlı Bir Çözüm
Monotonik çift uçlu kuyruk ile her pencereyi toplam O(n) zamanda, diziyi yalnızca bir kez tarayarak değerlendirebilirsiniz.
Dizinleri Yine Saklayın
Değerler yerine dizinleri çift uçlu kuyrukta tutun. Dizinler, ön taraftaki öğenin geçerli pencereden çıkıp çıkmadığını kontrol etmenizi sağlar.
from collections import deque
dq = deque()
res = []Azalan Sırayı Koruyun
Çift uçlu kuyruk, önden arkaya doğru değere göre azalan kalır; böylece öndeki dizin her zaman pencerenin maksimumunu gösterir.
Daha Küçük Kuyruk Sonlarını Atın
i dizinini eklemeden önce, bu değerler daha küçük olduğu sürece arkadan pop yapın; çünkü bunlar gelecekteki bir maksimum olamaz.
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()Yeni Dizini Ekleyin
Zayıf kuyruk sonlarını temizledikten sonra geçerli dizini append ile ekleyin. Çift uçlu kuyruğun sırası sonraki adımlar için doğru kalır.
dq.append(i)Eskimiş Önü Atın
Öndeki dizin pencerenin dışına çıkarsa onu popleft ile çıkarın. k boyutundaki bir pencere i eksi k artı 1 dizininde başlar.
if dq[0] <= i - k:
dq.popleft()Her Maksimumu Kaydedin
İlk tam pencere k eksi 1 dizininde oluştuğunda, çift uçlu kuyruğun önü bundan sonraki her konumun yanıtını tutar.
if i >= k - 1:
res.append(nums[dq[0]])Çıkarma Sırasına Dikkat Edin
Yanıtı okumadan önce eskimiş önü atın. Aksi hâlde pencereden çoktan çıkmış bir maksimumu bildirebilirsiniz.
Doğrusal Süre Neden Geçerlidir
Her dizin en fazla bir kez eklenip çıkarılır; bu nedenle çift uçlu kuyruk işlemleri adım başına amortismanlı O(1), toplamda ise O(n) olur.
Minimum Pencere, Aynı Fikir
Kayan pencerenin minimumu için bunun yerine çift uçlu kuyruğu artan sırada tutun. Arka tarafı budarken karşılaştırmayı tersine çevirmeniz yeterlidir.
while dq and nums[dq[-1]] >= nums[i]:
dq.pop()Hızlı Kontrol
Kayan pencere maksimumunda monotonik çift uçlu kuyruğun önü neyi tutar?
Özet: Çift Uçlu Kuyruk Pencereyi Kazanır
Dizinlerden oluşan azalan bir çift uçlu kuyruk tuttunuz: küçük kuyruk sonlarını budayın, eskimiş önü atın ve O(n) zamanda her pencerenin maksimumu için önü okuyun. 🏆
Sıkça Sorulan Sorular
“Deque ile Kayan Pencere Maksimumu” dersi ücretsiz mi?
Evet — “Deque ile Kayan Pencere Maksimumu” 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 Competitive Programming Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Competitive Programming Academy kursu toplamda 4 dersten oluşur.
“Deque ile Kayan Pencere Maksimumu” dersinde ne öğreneceğim?
Pencerenin uç değerlerini O(n) içinde koruyun. Competitive Programming Academy 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.
Competitive Programming Academy öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Competitive Programming Academy, 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 4. dersidir.
“Deque ile Kayan Pencere Maksimumu” 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 Competitive Programming Academy dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Competitive Programming Academy 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
- Eşleşen Köşeli Ayraçlar için Yığınlar
- Tekdüze Yığın: Sonraki Büyük Öğe
- Kuyruklar ve collections.deque
- Deque ile Kayan Pencere Maksimumu