***Sliding Window Maximum (Leetcode 239)

Very Important Question. Understand how deque is used here

Problem Link: https://leetcode.com/problems/sliding-window-maximum/

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ans=[]
        deq=[]
        i=0
        j=0
        n=len(nums)
        while(j<n):
            if(len(deq)==0):
                deq.append(nums[j])
            else:
            ### If the new element is greater than the top of queue,
            ### we do not need that top element anymore.
                while(len(deq)>0 and deq[len(deq)-1]<nums[j]):
                    deq.pop()
                deq.append(nums[j])
            
            if(j-i+1<k):
                j+=1
            
            elif(j-i+1>=k):
                
                ans.append(deq[0])
                
                if(nums[i]==deq[0]):
                    del deq[0]
                
                i+=1
                j+=1
        return ans

Last updated