239. Sliding Window Maximum

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.

My Answer 1: Time Limit Exceeded (49 / 60 test cases passed.)

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        result = []
        
        for i in range(len(nums)-k+1):
            result.append(max(nums[i:i+k]))
        
        return result

nums[i:i+k] 로 k 개만큼 묶어서 최댓값만 result 에 넣어줌

My Answer 2: Time Limit Exceeded (58 / 60 test cases passed.)

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if len(nums) <= k:
            return [max(nums)]
        if k == 1:
            return nums
        
        result = []
        
        m = max(nums[:k])
        result.append(m)
        for i in range(k, len(nums)):
            if nums[i] > m:
                result.append(nums[i])
                m = nums[i]
            else:
                if nums[i-k] == m:
                    m = max(nums[i-k+1:i+1])
                result.append(m)
        
        return result

최댓값인 m 값을 업데이트 하는 식으로 함..
m 이 window 안을 벗어나면 => nums[i-k] == m 다음 window 의 max 값을 찾아서 바꿔줌

근데... 타임리밋~~
어떤 걸 써야할까...

Solution 1: Runtime: 1576 ms - 60.73% / Memory Usage: 29.3 MB - 99.12%

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ## RC ##
        ## APPROACH : DEQUE ##
        """
            ## LOGIC ##
            1. For the First k numbers we can directly find maximum and store, but the when the window slides by one position, the first element is removed. 
                What if the first number is the maximum of 0 to K ? How do we know the second maximum when first element is removed ? ( consider this example: [5, 2, 3, -1] and k = 3 ans = [5, 3] )
                So, For that we need to maintain some storage, here we use deque.
            2. Our Deque will always have the maximum at the start and we append small elements next to it. 
                ( if deque(for now, say we have numbers in it) is [4,1,0] and incoming curr num is 2, pop all nums smaller from backside i.e deque will be [4, 2] )
            3. And when the window slides, we remove all the numbers from front of deque if they donot fall under this window size.

            Example : [1,3,1,2,0,5] 3
            deque([0])              [1]
            deque([1])              [1, 3]
            deque([1, 2])           [1, 3, 3]
            deque([1, 3])           [1, 3, 3, 3]
            deque([3, 4])           [1, 3, 3, 3, 2]
            deque([5])              [1, 3, 3, 3, 2, 5]

            ## TIME COMPLEXITY : O(N) ##
            ## SPACE COMPLEXITY : O(k) ##
        """
        deque = collections.deque()
        res = []
        for i, num in enumerate(nums):
            while(deque and nums[deque[-1]] < num):
                deque.pop()     # 2
            if(deque and i - deque[0] >= k):
                deque.popleft() # 3
            deque.append(i)
            res.append(nums[deque[0]])
            # print(deque, res)
        return res[k-1:]

deque([a, b]) 는 [최댓값idx, 지금보고있는idx] 같은데............

k-1 개 까지는 res 에 그냥 넣어주고 마지막에 리턴할 때 res[k-1:] 을 리턴해줌

while(deque and nums[deque[-1]] < num):
=> num 보다 작은 숫자는 deque 에서 모두 pop

if(deque and i - deque[0] >= k):]
=> 최댓값인 deque[0] 이 window 를 벗어나면 popleft 해서 최댓값 바꿔줌