Leetcode 239 Sliding Window Maximum

Soru

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Örnek 1

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Örnek 2

Input: nums = [1], k = 1
Output: [1]

Çözüm

• Verilen bir tam sayı dizisi ve bir pencere boyutu k için, her pencere pozisyonunda maksimum değeri bulmanızı isteyen bir problem. Bu, bir dizide belirli bir boyutta sürekli kaydırılan bir pencerenin her adımında en büyük değeri belirlemeniz gerektiği anlamına gelir.
• Girdi: Tam sayılardan oluşan bir dizi nums ve bir pencere boyutu k.
• Çıktı: Her pencere için en büyük değeri içeren bir tam sayı dizisi.
• Bu problem genellikle bir çift yönlü kuyruk (deque) kullanılarak çözülür. Deque, her pencere için maksimum değeri verimli bir şekilde bulmamızı sağlar çünkü her adımda en büyük değere hızlıca erişebilir ve eski değerleri çıkarabiliriz. Deque, yalnızca en büyük değer adaylarını ve bunların indekslerini saklar, böylece dizinin kaydırılması sırasında en büyük değeri hızlıca güncelleyebiliriz.
• Çalışma Mekanizması:
• Deque Kullanımı: Deque, mevcut pencere içinde en büyük değerin indekslerini tutar.
• Geçersiz İndeksleri Çıkarma: Eğer deque’nun başındaki indeks mevcut pencere dışındaysa, çıkarılır.
• Değeri Karşılaştırma ve Ekleme: Mevcut değer, deque’nun sonundaki değerden büyükse, deque’nun sonundakiler çıkarılır, çünkü yeni değer daha büyük bir maksimum adayıdır.
• Sonuçların Güncellenmesi: İlk pencereden itibaren, her adımda deque’nun başındaki değer, en büyük değer olarak sonuç listesine eklenir.

Code

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums, k):
        # Sonuç listesi ve deque
        deq = deque()
        maxima = []

        for i in range(len(nums)):
            # Deque'nun solundaki indeks geçerliliğini kaybettiğinde çıkar
            if deq and deq[0] == i - k:
                deq.popleft()

            # Yeni eleman daha büyükse eski maksimum adaylarını deque'den çıkar
            while deq and nums[i] > nums[deq[-1]]:
                deq.pop()

            # Yeni elemanın indeksini ekle
            deq.append(i)

            # İlk pencereden sonra maksimumu sonuç listesine ekle
            if i >= k - 1:
                maxima.append(nums[deq[0]])

        return maxima

     
        

Complexity

• Time complexity (Zaman Karmaşıklığı) : O(n), burada n nums dizisinin uzunluğudur. Her eleman için sabit sayıda işlem yapılır (her eleman yalnızca bir kez deque’ye eklenir ve bir kez çıkarılır).
• Space complexity (Alan Karmaşıklığı) : O(k), burada k pencere boyutudur. Deque, en kötü durumda pencere boyutuna eşit sayıda eleman içerebilir.