Sliding Window Maximum
Bir tamsayı dizisi nums ve k pencere boyutu veriliyor. k ardışık değerden oluşan bir pencere sol uçta başlar ve sağ kenarı son değerin üzerine gelene kadar her seferinde bir konum sağa ilerler. Soldan sağa her konumda penceredeki en büyük değeri döndürün: uzunluğu n olan bir dizi için n-k+1 değer.
Fonksiyon
- numsinteger-array
- dizinin üzerinde kaydığı pencere
- 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 × 104-104 ≤ nums[i] ≤ 104- Sonuç, soldan sağa sırayla her pencere için bir tane olmak üzere
nums.length-k+1değ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çindedir, bu yüzden her biri 12 yanıtını verir. Pencereden çıktıktan sonra,
[3, 8, 5]ve[8, 5, 1]dizilerinin her 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]. İki negatif sayıdan en büyüğü 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
kdizinin uzunluğuna eşit olduğunda, dizinin tamamından oluşan tek bir pencere vardır. En büyük değeri 6'dır; 6'nın ikinci kopyası ikinci bir sonuç eklemez.
Ek soru
Arkaya bir değer eklemeyi, öndeki değeri kaldırmayı ve mevcut maksimum değeri okumayı, her birini amortize edilmiş O(1) zamanda destekleyen bir kuyruk oluşturabilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Her pencereyi en büyük değeri bulmak için taramak, pencere başına
kadım gerektirir. Komşu iki pencereyi karşılaştır:k-1değeri paylaşırlar; çünkü soldan bir değer çıkar ve sağdan bir değer girer.Yeni bir değer geldiğinde, penceredeki ondan küçük veya ona eşit olan tüm eski değerler bir daha asla maksimum olamaz. Eski değeri hâlâ içeren sonraki her pencerede yeni değer de bulunur ve en az onun kadar büyüktür. Bu eski değerleri kalıcı olarak atabilirsiniz.
Çift uçlu kuyrukta kalan değerlerin indislerini tut; değerleri önden arkaya doğru kesin olarak azalsın. Her yeni indis için arkadaki daha küçük veya eşit değerleri çıkar, indisi ekle, pencereden çıkmışsa öndekini çıkar ve pencerenin maksimum değerini önden oku.
Çözüm
Komşu pencereler k-1 değeri paylaşır; bu yüzden her maksimumu yeniden hesaplamak, işin neredeyse tamamını tekrarlar. Ancak bir maksimum geri alınamaz: en büyük değer pencerenin dışına kaydığında, pencereyi yeniden okumadan sıradaki en büyük değere ihtiyacın olur. Monoton bir deque, yalnızca hâlâ maksimum olabilecek değerleri tutar; yanıt da deque'nin önündedir.
Her pencereyi tara
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Her pencerenin k değerini oku ve en büyüğünü sakla. Her pencerenin tamamı okunduğundan, maksimum değer gözden kaçamaz. n-k+1 pencerenin her biri k okuma gerektirir; bu, k değeri n değerinin yaklaşık yarısı olduğunda en kötü durumdur: n = 2 × 10^4 ve k = 10^4 için, her biri 10^4 değer içeren yaklaşık 10^4 pencere, yani 10^8 okuma gerekir.
Algoritma
startdeğerini 0'dann-kdeğerine kadar döngüye sok.nums[start]ilenums[start+k-1]arasındaki en büyük değeri al.- Bunu sonuca ekle ve döngüden sonra 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 resultHer iki taraftaki maksimum değerleri içeren bloklar
Sezgi
Diziyi k uzunluğundaki bloklara böl: 0'dan k-1'e kadar olan indeksler, ardından k'den 2k-1'e kadar olanlar ve böyle devam eder; k, n'i tam bölmüyorsa son blok daha kısa olur. Bir pencerenin uzunluğu tam olarak k'dir; dolayısıyla ya tek bir bloğun tamamını ya da bir bloğun sonu ile sonraki bloğun başlangıcını kapsar.
Bu nedenle, fromStart[i] değerini, i'nin bloğunun başlangıcından i'ye kadar olan en büyük değer; toEnd[i] değerini ise i'den bloğunun sonuna kadar olan en büyük değer olarak önceden hesapla. i'de başlayan pencere i+k-1'de biter: toEnd[i] sol kısmı, fromStart[i+k-1] ise sağ kısmı kapsar; bu nedenle büyük olan, pencerenin maksimumudur. İlk örnekte [2, 12, 3] penceresi toEnd[1] = 12 ve fromStart[3] = 3 değerlerini alır ve sonuç 12 olur.
Üç geçiş O(n) zaman alır; bunun karşılığında uzunluğu n olan iki yardımcı dizi gerekir ve ilk yanıtı vermeden önce dizinin tamamının elde bulunması gerekir.
Algoritma
fromStartdizisini soldan sağa doldurun;i,k'nin katı olduğundanums[i]ile yeniden başlayın.toEnddizisini sağdan sola doldurun; son indekste vei+1,k'nin katı olduğundanums[i]ile yeniden başlayın.- 0'dan
n-k'ye kadar her başlangıçiiçintoEnd[i]ilefromStart[i+k-1]değerlerinden büyük olanı ekleyin.
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
j indeksi i'den önce geliyorsa ve nums[j] ≤ nums[i] ise, j bir daha asla maksimum olamaz: j'yi içeren sonraki her pencere, daha sonra çıkan i'yi de içerir. Bu yüzden i geldiğinde j'yi unutabilirsin.
Henüz unutulmayan indekslerden oluşan bir çift uçlu kuyruk tut. i geldiğinde, değerleri nums[i]'den küçük veya eşit olan indeksleri kuyruk sonundan çıkar, ardından i'yi ekle. Geriye kalan değerler önden arkaya doğru kesin olarak azalır; bu nedenle kuyruk başı pencerenin maksimumudur. İndeksleri sakla, çünkü pencere onu geçtiğinde kuyruk başındaki indeksin de çıkması gerekir. İlk örnekte, 5. indekste kuyrukta 12, 8 ve 5 bulunur; 12, 5 - 3 = 2 indeksinde yer alır, bu yüzden çıkar ve yanıt 8 olur.
Her indeks bir kez eklenir ve en fazla bir kez çıkarılır: en fazla 2n kuyruk işlemi, O(n) zaman. Kuyrukta hiçbir zaman k indeksten fazlası bulunmaz.
Algoritma
- Her
iindeksi için, arka uçtaki değernums[i]değerinden küçük veya eşit olduğu sürece ve çift uçlu kuyruk boş değilken arka taraftan indeksleri çıkarın. ideğerini arka tarafa ekleyin.- Ön taraftaki indeks
i-kdeğerine eşitse, pencereden çıkmıştır: onu çıkarın. i ≥ k-1olduğunda, ön taraftaki indeksin değerini sonuca ekleyin.
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
- İndeksler yerine değerleri saklamak.
[3, 1, 3]vek = 2için ikinci 3, ilkini deque'den çıkarır; ardındannums[0]'a, yani pencereden çıkan değere eşit olduğu için kendisi de kaldırılır. - Yanıtı çok erken ya da çok geç vermek. İlk tam pencere
k-1indeksinde sona erer ve sonuç tam olarakn-k+1değer içermelidir. i-kyerinei-k+1indeksini pencereden çıkarmak. Bu indeks hâlâ pencerenin ilk değeridir.- Deque'in arkasında bir öğe olup olmadığını kontrol etmeden oradaki öğeyi okumak.
- Blok yaklaşımında son bloğun
k'den 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 sorular3
Sliding Window Maximum'ın zaman karmaşıklığı nedir?
Monotonik çift uçlu kuyruk çözümü O(n) zamanda çalışır; çünkü her indeks kuyruğa bir kez eklenir ve en fazla bir kez çıkarılır. Kuyruk en fazla k indeks tutar, bu nedenle sonuç için gereken alanın üzerine ek olarak O(k) alan gerekir.
Kayar Pencere Maksimumu bir yığın kullanılarak çözülebilir mi?
Evet. Değer ve indeks çiftlerini bir maksimum yığına ekle ve tepeyi okumadan önce, indeksi pencerenin dışındaysa tepeden çıkar. Bu işlem O(n log n) zamanda çalışır ve en fazla n öğe tutabilir. Daha büyük bir değer gelir gelmez işe yaramayan değerleri attığı için deque daha hızlı ve daha küçüktür.
Monotonik bir deque ile monotonik bir yığın arasındaki fark nedir?
Deque'in arka tarafı monotonik 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 önden bir çıkış ekler. Sonraki daha büyük elemanın süresi dolmaz, bu yüzden yalnızca yığına ihtiyaç duyar. Karşılaştırmayı tersine çevir ve deque her pencerenin minimumunu verir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def maxSlidingWindow(nums, k):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argümanlar
nums = [4, 2, 12, 3, 8, 5, 1] k = 3
Beklenen Çıktı
[12, 12, 12, 8, 8]