***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
PreviousMinimum Difference Between Largest and Smallest Value in Three Moves (Leetcode 1509)NextVariable Size Sliding Window Pattern
Last updated