Deque ile Kayan Pencere Maksimumu
Pencerenin uç değerlerini O(n) içinde koruyun.
Deque ile Kayan Pencere Maksimumu, CoddyKit'te ücretsiz bir Coding Interview Prep 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, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep 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. 🏆
Yapay zeka eğitmeniyle Coding Interview Prep öğren — ücretsiz
Tarayıcında gerçek kod yaz ve çalıştır, 7/24 yapay zeka eğitmeninden anında yardım al; web'de ya da uygulamada kaldığın yerden devam et.
- Kurslar
- 90
- Dersler
- 360
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 Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Deque ile Kayan Pencere Maksimumu” dersinde ne öğreneceğim?
Pencerenin uç değerlerini O(n) içinde koruyun. Coding 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.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding 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 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 Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding 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
- 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