239. Sliding Window Maximum

from collections import deque
class Monoque:
    def __init__(self):
        self.q = deque()
        
    def push(self,num):
        # ensure numbers in queue is decreasing, pop off smaller numbers before push curren number in 
        while self.q and self.q[-1] < num:
            self.q.pop()
        self.q.append(num)
        
    def max(self):
        # since queue is monotical decreasing, q bottom is biggest 
        return self.q[0]
    
    def pop(self,num):
        # when que bottom is same as transition number, q need to pop it off, else it may have already been removed 
        if self.q and self.q[0] == num:
            self.q.popleft()
        
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # step1: initialize a special  queue, result
        window = Monoque()
        res = []
        #step2 loop through whole nums
        for i in range(len(nums)):
            #step3 keep pushing into q until reached window size 
            if i < k-1 :
                window.push(nums[i])
            # step4: after reaching window size, get window max, save it to result. then pop off window left number
            else:
                # window start move forward 
                window.push(nums[i])
                res.append(window.max())
                window.pop(nums[i-k+1])
        # step5: return res 
        return res 

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # time O(N) space O(N)
        # step1: initialize res  and q
        q = collections.deque()
        res = []
        for idx, val in enumerate(nums):
            #step2: before append, remove small vals in the q 
            while q and nums[q[-1]] < val:
                q.pop()
            q.append(idx)
            # check if window size has reached k 
            if idx-q[0] == k:
                q.popleft()
            
            # check if it's time to put into res 
            if idx >= k-1:
                res.append(nums[q[0]])
        return res