LC239. Sliding Window Maximum

Approach 1: Optimal

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # Monotonic decreasing queue, front of queue has largest
        # element in the window
 
        # Two approaches that work for this problem:
        # a) store indices of elements
        # b) store the elements themselves *
        mdq = deque()
 
        l = r = 0
        output = []
 
        for r in range(len(nums)):
            while mdq and nums[r] > mdq[-1]:
                mdq.pop()
            
            mdq.append(nums[r])
            
            # Only start appending to result and incrementing
            # left once we have a valid window of k elements.
            if r >= k - 1:
                output.append(mdq[0])
 
                l += 1
                # Was the previous left element the greatest element
                # in the window? Then dequeue/pop from left.
                if nums[l - 1] == mdq[0]:
                    mdq.popleft()
        
        return output

Complexity

Time: $O(n)$
Space: $O(k)$

Other Languages