239. Sliding Window Maximum

from collections import deque
class MaxMonoQueue:
    # Invariant: all preceeding numbers that are < newVal need to get out!
    def __init__(self):
        self.queue = deque()
    def enqueue(self, val, idx):
        # maintaining the invariant
        while self.queue and self.queue[-1][0] <= val:
            self.queue.pop()
        self.queue.append((val, idx))
    def dequeue(self):
        if len(self.queue):
            return self.queue.popleft()
        return None
    def getHead(self):
        return self.queue[0] if len(self.queue) else None
    def __repr__(self):
        return str(self.queue)
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        '''
        
        k = 3
        sIdx = 0
        eIdx = 2
        
        [1,3,-1,-3,5,3,6,7]
        
        '''
        q = MaxMonoQueue()
        res = []
        N = len(nums)
        
        # window includes [startIdx, endIdx] inclusive!
        startIdx = 0
        endIdx = -1
        
        while endIdx < N - 1:
            endIdx += 1
            q.enqueue(nums[endIdx], endIdx)
            
            # Check to see if window is of size k.
            windowSize = endIdx - startIdx + 1
            
            # Still growing our window
            if windowSize < k:
                continue
            
            # window is of size k.
            # Get the max within the window, then append that to result
            res.append(q.getHead()[0])
            
            # you want to pop IF this element wasn't already popped off.
            if q.getHead()[1] == startIdx:
                q.dequeue()

            # maintains the same window size
            startIdx += 1
            
        return res