Kayan pencerede maksimum

Problem

Bir tamsayı dizisi ve bir pencere boyutu k veriliyor. k uzunluğundaki pencere dizinin başından sonuna birer adım kayıyor. Pencerenin her konumu için içindeki en büyük değeri bul ve bu maksimumları sırasıyla bir dizi olarak döndür. Sonuç dizisinin uzunluğu n - k + 1.

Girdi:  nums = [4, 2, 12, 3, 8, 1, 7], k = 3
Çıktı:  [12, 12, 12, 8, 8]
        [4 2 12] [2 12 3] [12 3 8] [3 8 1] [8 1 7]

Girdi:  nums = [5, 4, 3, 2, 1], k = 2
Çıktı:  [5, 4, 3, 2]

Netleştirme soruları

• k, 1 ile n arasında mı garanti? Değilse ne yapmalıyım?
• Negatif değerler ve tekrarlar var mı?
• n ve k ne kadar büyük? (n = 10⁵, k = 5×10⁴ olursa O(n × k) çok yavaş.)
• Veri bir dizi mi, yoksa sonsuz bir stream mi? (Deque çözümü stream'de de çalışır.)

İpuçları

Yaklaşım

Brute force: Her pencere için k elemanı tara. O(n × k) zaman. k = n/2 için O(n²).

Max-heap: (değer, index) çiftlerini bir heap'e at; tepedeki index pencerenin dışındaysa at (lazy deletion). O(n log n) zaman, O(n) bellek. Mülakatta iyi bir ara adım ve çoğu zaman kabul edilir. TreeMap<değer, adet> ile de O(n log k) yapılabilir.

Optimal, monoton deque: Kilit gözlem: j > i ve nums[j] >= nums[i] ise, i artık hiçbir pencerenin maksimumu olamaz. Çünkü i'yi içeren her gelecek pencere j'yi de içerir (j daha geç çıkar) ve j en az onun kadar büyüktür. Bu yüzden i güvenle atılabilir.

Deque'de index'leri tutarız; değerleri önden arkaya kesin azalan sıradadır:

1. Öndeki index pencerenin dışına düştüyse (<= i - k) önden at.
2. Arkadan, değeri yeni elemandan küçük ya da eşit olanları at.
3. Yeni index'i arkaya ekle.
4. İlk pencere dolduysa (i >= k - 1) maksimum, öndeki index'in değeridir.

Deque'de değer yerine index tutmak gerekir; değer tutarsan bir elemanın pencereden çıkıp çıkmadığını bilemezsin (özellikle tekrar eden değerlerde).

Eşitlikte arkadan atmak (<=) ya da tutmak (<) ikisi de doğru sonuç verir; <= deque'yi daha kısa tutar.

Java çözümü

import java.util.ArrayDeque;
import java.util.Deque;

public final class SlidingWindowMaximum {

    public int[] maxSlidingWindow(int[] nums, int k) {
        if (k <= 0 || k > nums.length) {
            throw new IllegalArgumentException("k must be in [1, nums.length]");
        }
        int[] result = new int[nums.length - k + 1];
        Deque<Integer> candidates = new ArrayDeque<>();            // index'ler; değerleri azalan sırada
        for (int i = 0; i < nums.length; i++) {
            if (!candidates.isEmpty() && candidates.peekFirst() <= i - k) {
                candidates.pollFirst();                            // pencereden çıkan en eski index
            }
            while (!candidates.isEmpty() && nums[candidates.peekLast()] <= nums[i]) {
                candidates.pollLast();                             // yeni gelen daha büyükse onlar asla max olamaz
            }
            candidates.offerLast(i);
            if (i >= k - 1) {
                result[i - k + 1] = nums[candidates.peekFirst()];
            }
        }
        return result;
    }
}

k geçersizse exception fırlatmayı seçtim; LeetCode 1 <= k <= n garanti eder, ama bir kütüphane metodunda sessizce boş dizi döndürmek hatayı gizler.

Karmaşıklık

• Zaman: O(n) amortize. Her index deque'ye bir kez girer ve en fazla bir kez çıkar; iç while döngüsünün toplam maliyeti O(n).
• Bellek: O(k) deque için (sonuç dizisi hariç).
• Heap versiyonu O(n log n) zaman, O(n) bellek; TreeMap versiyonu O(n log k).

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı; 3.000 rastgele girdide (n 1-25, k 1-n, negatif ve tekrarlı değerler) O(n × k) brute force ile karşılaştırıldı.

Mülakatçı için

Bu soru monoton deque kalıbını bilip bilmediğini ölçer; ama bilmeyen bir aday için heap çözümü de değerli bir sinyaldir. Asıl beklenti adayın "hangi elemanlar asla maksimum olamaz?" sorusunu kendisi sorması ve buradan bir değişmez (deque azalan) kurmasıdır. Amortize O(n) argümanını açıklayamayan aday iç içe while döngüsünü O(n × k) sanabilir; mutlaka sor.

İpucu zamanlaması: Aday brute force'ta kalırsa heap'i öner ya da "hangi veri yapısı maksimumu hızlı verir?" diye sor. Heap'li çözüm geldiyse pencereden çıkan elemanı nasıl sileceğini sor (PriorityQueue.remove(Object) O(k); lazy deletion daha iyi). Zaman kalırsa ikinci ipucuyla deque'ye yönlendir.

Takip soruları:

1. Aynı anda pencere minimumunu da istesem? (Beklenen: ikinci bir artan deque.)
2. Bu bir monitoring sistemi: son 5 dakikadaki en yüksek gecikme değeri her saniye raporlanacak ve olaylar düzensiz zamanlarda geliyor. (Beklenen: pencereyi index yerine zaman damgasıyla tanımla; önden atma koşulu ts <= now - 5dk; bellek pencere içindeki olay sayısıyla sınırlı.)
3. Pencere medyanı istenseydi deque işe yarar mı? (Beklenen: hayır, sıra istatistiği gerekir; iki heap + lazy deletion ya da TreeMap; LeetCode 480.)

Benzer problemler

• Sliding Window Median (LeetCode 480).
• Min Stack (LeetCode 155) ve Max Stack: "minimum/maksimumu takip eden yapı" fikri.
• Daily Temperatures (LeetCode 739): monoton stack (bu sette: daily-temperatures).
• Shortest Subarray with Sum at Least K (LeetCode 862): önek toplamı + monoton deque.
• Find Median from Data Stream (LeetCode 295) (bu sette: find-median-from-data-stream).