[LeetCode] 239. Sliding Window Maximum

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

Maintain a decreasing monotonic queue. The first item of the queue is the maximum value in the range of k numbers.

Time complexity = O ( N )

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        queue = deque()
        result = []
        
        for i in range(k):
            while queue and queue[-1][1] < nums[i]:
                queue.pop()
            
            queue.append((i, nums[i]))
        
        result.append(queue[0][1])
        
        for i in range(k, len(nums)):
            if i - queue[0][0] == k:
                queue.popleft()
            
            while queue and queue[-1][1] < nums[i]:
                queue.pop()
            
            queue.append((i, nums[i]))
            
            result.append(queue[0][1])
        
        return result

Edited on 10/09/2021. Update for the monotonic queue solution.