Sliding Window Maximum

Q: Sliding Window Maximum'ın zaman karmaşıklığı nedir?

Monotonik deque çözümü O(n) zamanda çalışır. Her indeks bir kez eklenir ve en fazla bir kez çıkarılır; bu nedenle tek bir adımda birden fazla eleman çıkarılabilse de iç döngü tüm çalışma boyunca en fazla n çıkarma işlemi yapar. Deque en fazla k indeks tutar, dolayısıyla sonuç için gereken alanın üzerine ek olarak O(k) alan gerekir.

ZorKayan pencere Monoton yığın Kuyruk

+10

Bir tamsayı dizisi nums ve k pencere boyutu veriliyor. Bir pencere, art arda gelen k değeri kapsar. Dizinin sol ucundan başlar ve sağ kenarı son değerin üzerine gelene kadar her seferinde bir konum sağa kayar.

Pencerenin her konumunda, içindeki en büyük değeri soldan sağa doğru içeren bir dizi döndürün. Uzunluğu n olan bir dizide n-k+1 pencere bulunur, dolayısıyla sonuç n-k+1 değer içerir.

Fonksiyon

maxSlidingWindow(nums: integer-array, k: integer) → integer-array

numsinteger-array: dizinin üzerinde pencerenin kaydığı
kinteger: her penceredeki değer sayısı
Döndürürinteger-array: en soldaki pencereden en sağdaki pencereye kadar her pencerenin en büyük değeri

Kısıtlar

1 ≤ k ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
Sonuç, soldan sağa sıralı olarak her pencere için bir tane olmak üzere nums.length-k+1 değer içerir.

Örnekler

Girdi: nums = [4, 2, 12, 3, 8, 5, 1]k = 3
Çıktı: [12, 12, 12, 8, 8]
Açıklama: 12 ilk üç pencerenin içinde yer alır: [4, 2, 12], [2, 12, 3] ve [12, 3, 8]. Pencereden çıktıktan sonra [3, 8, 5] ve [8, 5, 1] pencerelerinin ikisinde de en büyük değer 8'dir.

Girdi: nums = [-3, -1, -7, -2]k = 2
Çıktı: [-1, -1, -2]
Açıklama: Pencereler [-3, -1], [-1, -7] ve [-7, -2] şeklindedir. İki negatif sayıdan büyük olanı sıfıra daha yakın olandır; bu da -1, -1 ve -2 sonuçlarını verir.

Girdi: nums = [6, 6, 1]k = 3
Çıktı: [6]
Açıklama: k dizinin uzunluğuna eşit olduğunda tek bir pencere vardır: dizinin tamamı. En büyük değeri 6'dır ve 6'nın ikinci kopyası ikinci bir yanıt eklemez.

Gönderirken +15 gizli test

Ek soru

Arkaya bir değer eklemeyi, öndeki değeri çıkarmayı ve geçerli maksimum değerini okumayı, her birini amortize O(1) zamanda destekleyen bir kuyruk oluşturabilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Komşu pencereler k-1 değeri paylaşır; bu nedenle her maksimumu baştan hesaplamak, işin neredeyse tamamını tekrar etmene yol açar. Zor olan, maksimumun geri alınamamasıdır: en büyük değer soldan çıkınca, pencereyi yeniden okumadan sıradaki en büyük değeri bulman gerekir. Monotonik çift uçlu kuyruk, maksimum olma ihtimali hâlâ bulunan değerleri sıralı biçimde tutar; böylece yanıt her zaman kuyruğun başında olur ve her indeks kuyruğa bir kez girip bir kez çıkar.

Her pencereyi tara

Doğru, ama en büyük testlerde bitmiyor

Sezgi

En doğrudan fikir, ifadeyi izler. start dizininde başlayan pencere, start ile start+k-1 aralığını kapsar. Bu k değeri okuyun, en büyüğünü tutun ve başlangıç konumunu bir adım sağa kaydırın. 0'dan n-k'ye kadar n-k+1 başlangıç konumu vardır.

Tanım gereği doğrudur: her pencere baştan sona okunur, dolayısıyla en büyük değeri gözden kaçırmak mümkün değildir. Sonuç dışında gereken ek bellek, çalışan maksimum değer için tek bir değişkendir.

Yavaştır. n-k+1 pencerenin her biri k okuma gerektirir ve çarpım, k yaklaşık n'nin yarısı olduğunda en büyüktür. n = 2 × 10^4 ve k = 10^4 için bu, 10^4 değerlik 10^4 pencere, yani 10^8 okumadır. Daha da kötüsü, komşu iki pencere k-1 değeri paylaşır; bu nedenle okumaların neredeyse her biri, daha önce yaptığınız bir okumayı tekrarlar.

Algoritma

Boş bir sonuç listesi oluştur.
start değerini 0'dan n-k değerine kadar döngüye sok.
best değerini nums[start] olarak ayarla, ardından bunu nums[start+k-1] değerine kadar olan her değerle karşılaştır ve daha büyük olanı tut.
best değerini sonuca ekle.
Sonucu döndür.

def maxSlidingWindow(nums, k):
    result = []
    for start in range(len(nums) - k + 1):
        # Read all k values of this window again
        result.append(max(nums[i] for i in range(start, start + k)))
    return result

Her iki taraftaki maksimumlara sahip bloklar

Sezgi

Diziyi k uzunluğunda bloklara ayırın: 0'dan k-1'e kadar olan indisler, ardından k'den 2k-1'e kadar olanlar ve bu şekilde devam edin; n, k'nin katı değilse son blok daha kısa olur. Bir pencerenin uzunluğu tam olarak k olduğundan ya tek bir blokla eşleşir ya da bir bloğun sonunu ve sonraki bloğun başını kapsar. Üç bloğa hiçbir zaman dokunmaz.

Bu, iki dizi kullanmayı öneriyor. fromStart[i], i'nin bloğunun başından i'ye kadar olan en büyük değerdir; soldan sağa doldurulur ve her blok başlangıcında sıfırlanır. toEnd[i], i'den bloğunun sonuna kadar olan en büyük değerdir; sağdan sola doldurulur ve her blok sonunda sıfırlanır. i'de başlayan pencere i+k-1'de biter. Sol kısmı toEnd[i], sağ kısmı ise fromStart[i+k-1] tarafından kapsanır; dolayısıyla pencerenin maksimumu bu ikisinden büyük olanıdır. Pencere tek bir bloğun tamamı olduğunda, her iki yarı da o bloğun maksimum değerini verir ve yanıt yine doğrudur.

nums = [4, 2, 12, 3, 8, 5, 1] ve k = 3 için bloklar [4, 2, 12], [3, 8, 5] ve [1] olur. fromStart dizisi [4, 4, 12, 3, 8, 8, 1], toEnd dizisi ise [12, 12, 12, 8, 8, 5, 1] olur. [2, 12, 3] penceresi 1'de başlar: toEnd[1] = 12, 2 ve 12'yi kapsar; fromStart[3] = 3, 3'ü kapsar ve yanıt 12'dir.

Bu yöntem O(n) zamanda, dizi üzerinde üç geçişte çalışır. Bedeli, uzunluğu n olan iki yardımcı dizidir ve ilk pencereyi yanıtlayabilmek için dizinin tamamına ihtiyaç duyar.

Algoritma

fromStart dizisini soldan sağa doldur: i, k'nin katıysa nums[i]'yi kopyala; değilse fromStart[i-1] ile nums[i] değerlerinden büyüğünü al.
toEnd dizisini sağdan sola doldur: i son indeksse veya i+1, k'nin katıysa nums[i]'yi kopyala; değilse toEnd[i+1] ile nums[i] değerlerinden büyüğünü al.
0'dan n-k'ye kadar olan her başlangıç i için toEnd[i] ile fromStart[i+k-1] değerlerinden büyüğünü ekle.
Sonucu döndür.

def maxSlidingWindow(nums, k):
    n = len(nums)
    # Cut nums into blocks of k: indices 0..k-1, k..2k-1, and so on.
    from_start = [0] * n  # max from the start of i's block up to i
    to_end = [0] * n      # max from i up to the end of i's block
    for i in range(n):
        if i % k == 0:
            from_start[i] = nums[i]
        else:
            from_start[i] = max(from_start[i - 1], nums[i])
    for i in range(n - 1, -1, -1):
        if i == n - 1 or (i + 1) % k == 0:
            to_end[i] = nums[i]
        else:
            to_end[i] = max(to_end[i + 1], nums[i])
    # A window [i, i+k-1] is the tail of one block plus the head of the next.
    return [max(to_end[i], from_start[i + k - 1]) for i in range(n - k + 1)]

İndislerden oluşan monotonik çift uçlu kuyruk

Sezgi

Tek bir gözlemle başlayın. j indeksi i indeksinden önce geliyor ve nums[j] ≤ nums[i] olsun. j'yi hâlâ içeren sonraki her pencere, i'yi de içerir; çünkü i daha sağdadır ve pencereden daha sonra çıkar. Bu pencerelerin hepsinde nums[i] en az o kadar büyüktür; dolayısıyla j bir daha asla en büyük değer olamaz. i geldiği anda j işe yaramaz hâle gelir ve onu unutabilirsiniz.

Unutmadığınız indeksleri çift uçlu bir kuyrukta tutun. i geldiğinde, değerleri nums[i]'den küçük veya ona eşit olduğu sürece sondan indeksleri çıkarın, ardından i'yi ekleyin. Böylece geriye kalanların değerleri önden arkaya doğru kesin olarak azalan sırada olur; çünkü daha büyük olmayan eski herhangi bir değer kuyruktan çıkarılmıştır. Bu nedenle en büyük değer öndedir. Kuyruk değerleri değil indeksleri tutar; çünkü pencere onu geçtiğinde öndeki indeks de çıkmalıdır: i'de biten pencere i-k+1'de başlar, yani pencereden çıkan indeks i-k'dir; öndeyse onu çıkarırsınız.

nums = [4, 2, 12, 3, 8, 5, 1] dizisini k = 3 ile izleyin ve kuyruktaki değerleri listeleyin. 4 girer: [4]. 2 daha küçüktür, bu yüzden arkasında bekler: [4, 2]. 12 ikisini de çıkarır: [12] ve ilk pencerenin yanıtı 12 olur. 3 bekler: [12, 3], yanıt 12. 8, 3'ü çıkarır: [12, 8], yanıt 12. 5 bekler: [12, 8, 5]; ancak 12, 2. indekste durur ve 5. indekste biten pencere 3. indekste başlar, dolayısıyla 12 pencereden çıkmıştır: [8, 5], yanıt 8. 1 bekler: [8, 5, 1], yanıt 8.

Bunun neden O(n) olduğunu görelim: İç döngü tek bir adımda birkaç indeks çıkarabilir, ancak her indeks bir kez eklenir ve en fazla bir kez çıkarılır; ya daha büyük bir değer onu geçtiği için arkadan ya da pencereden çıktığı için önden. Tüm çalışmadaki çıkarmaların toplamı en fazla n olduğundan, toplam iş en fazla 2n kuyruk işlemidir. Kuyruktaki her indeks geçerli pencerenin içinde yer alır; bu nedenle kuyrukta hiçbir zaman k taneden fazla indeks bulunmaz.

Algoritma

İndeksler için boş bir çift uçlu kuyruk ve boş bir sonuç listesi oluştur.
Her i indeksi için, çift uçlu kuyruk boş değilken ve arka ucundaki değer en fazla nums[i] değerine eşitken arka uçtaki indeksleri çıkar.
i değerini arka uca ekle.
Ön uçtaki indeks i-k değerine eşitse, pencereden çıkmıştır: onu ön uçtan çıkar.
i ≥ k-1 olduğunda tam bir pencere i indeksinde sona erer: ön uçtaki indeksin değerini sonuca ekle.
Sonucu döndür.

from collections import deque


def maxSlidingWindow(nums, k):
    window = deque()  # indices; their values strictly decrease from front to back
    result = []
    for i, x in enumerate(nums):
        # A value at the back that is not bigger than x can never be a maximum again.
        while window and nums[window[-1]] <= x:
            window.pop()
        window.append(i)
        # The front index has slid out of the window on the left.
        if window[0] == i - k:
            window.popleft()
        # From index k-1 on, every step completes a window; its maximum sits at the front.
        if i >= k - 1:
            result.append(nums[window[0]])
    return result

Tuzaklar ve uç durumlar

Hataların çoğu pencerenin sınırlarından veya çift uçlu kuyruğun sakladığı değerlerden kaynaklanır.

İndeksler yerine değerleri saklamak. Bu durumda, ön eleman nums[i-k]'ye eşit olduğunda onu kuyruktan çıkarırsın ve yinelenen değerler soruna yol açar. [3, 1, 3] ve k = 2 için ikinci 3 ilkini kuyruktan çıkarır ve sonra kendisi de kaldırılır, çünkü pencereden çıkan değerle eşittir. İndeksleri sakla ve ön elemanı i-k ile karşılaştır.
Yanıtı çok erken veya çok geç vermek. İlk tam pencere k indeksinde değil, k-1 indeksinde sona erer ve sonuç tam olarak n-k+1 değer içermelidir.
Yanlış indeksi çıkarmak. i indeksinde sona eren pencere i-k+1 indeksinde başlar; bu nedenle pencereden çıkan indeks i-k'dir. i-k+1'i çıkarmak, hâlâ pencerede olan bir değeri kaldırır.
Boş bir çift uçlu kuyruğun arka veya ön elemanını okumak. Arka elemanıyla karşılaştırmadan önce kuyruğun bir şey içerip içermediğini kontrol et.
Çift uçlu kuyruğu pencerenin bir kopyası gibi görmek. Kuyruk yalnızca adayları, 1 ile k arasında sayıda indeksi tutar; dolayısıyla boyutu pencere hakkında hiçbir şey söylemez.
Blok yaklaşımında son bloğun k değerinden kısa olabileceğini unutmak. Sağdan sola geçiş, her blok sonunda olduğu gibi son indekste de yeniden başlamalıdır.

Sıkça sorulan sorular4

Sliding Window Maximum'ın zaman karmaşıklığı nedir?

Monotonik deque çözümü O(n) zamanda çalışır. Her indeks bir kez eklenir ve en fazla bir kez çıkarılır; bu nedenle tek bir adımda birden fazla eleman çıkarılabilse de iç döngü tüm çalışma boyunca en fazla n çıkarma işlemi yapar. Deque en fazla k indeks tutar, dolayısıyla sonuç için gereken alanın üzerine ek olarak O(k) alan gerekir.

Sliding Window Maximum, bir yığın kullanılarak çözülebilir mi?

Evet. Değer ve indeks çiftlerini bir maksimum yığına ekle. Tepeyi okumadan önce, indeksi pencerenin dışındaysa tepeden çıkar; çünkü eski girdiler yalnızca tepeye ulaştıklarında kaldırılır. Bu işlem O(n log n) zamanda çalışır ve en fazla n girdi tutabilir. Çift uçlu kuyruk daha hızlı ve daha küçüktür; çünkü daha büyük bir değer gelir gelmez işe yaramayan değerleri kaldırır.

Deque neden değerleri değil de indeksleri saklar?

Ön eleman, pencere onu geçtiğinde çıkmalıdır ve bunu yalnızca indeksi söyler. Yalnızca değerlere bakarak nums[i-k] ifadesinden tahmin yürütmeniz gerekir; aynı değer birden fazla kez göründüğünde bu işe yaramaz. İndeks, değeri de ek bir maliyet olmadan verir: nums[index].

Monotonik kuyruk ile monotonik yığın arasındaki fark nedir?

Deque’in arka tarafı monoton bir yığın gibi çalışır: bir değeri eklemeden önce, işe yaramaz hâle getirdiği değerleri çıkarırsın. Deque, çok eski değerler için ön tarafta ikinci bir çıkış ekler. Sonraki daha büyük elemanı bulmak gibi süresi dolmayan bir problem yalnızca yığını gerektirir; kayan pencere ise her iki ucu da gerektirir. Karşılaştırmayı tersine çevirince aynı kod her pencerenin minimumunu verir.

Python

def maxSlidingWindow(nums, k):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

nums = [4, 2, 12, 3, 8, 5, 1]
k = 3

Beklenen

[12, 12, 12, 8, 8]

Sliding Window Maximum

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her pencereyi tara

Her iki taraftaki maksimumlara sahip bloklar

İndislerden oluşan monotonik çift uçlu kuyruk

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler