classSolution:defmaxSlidingWindow(self,nums:List[int],k:int)->List[int]:ans,window=[],[]# Record the indices whose nums are in descending orderforiinrange(len(nums)):# Remove the index whose elements < the new numwhilewindowandnums[i]>nums[window[-1]]:window.pop()# Add the index of the new numwindow.append(i)# if the size of the window > k, pop the first index in the windowifi-window[0]+1>k:window.pop(0)# Add the first element after the window is formedifi>=k-1:ans.append(nums[window[0]])returnans
importqueueclassMaxQueue:def__init__(self):self.queue=queue.Queue()self.deque=queue.deque()# Double-ended queue, the left is always the largestdefmax_value(self)->int:returnself.deque[0]ifself.dequeelse-1defpush_back(self,value:int)->None:self.queue.put(value)whileself.dequeandself.deque[-1]<value:self.deque.pop()self.deque.append(value)defpop_front(self)->int:ifself.queue.empty():return-1val=self.queue.get()ifval==self.deque[0]:self.deque.popleft()returnval
Explanation
Time Complexity
max_value: O(1)
pop_front: O(1)
push_back: O(1)
For example, 543216,the last push_back takes O(N) and the rest of each only needs O(1). So the average is (O(1)*(N-1)+O(N))/N=O(1).