Problem statement

https://binarysearch.com/problems/Sliding-Window-Max/

Solution

Equal to Leetcode Leetcode 0239. Sliding Window Maximum

Complexity

Time complexity is O(n), because we iterate over our elements and for each element it can be put inside and outside of our deque only once. Space complexity is O(k), the maximum size of our deque.

Code

class Solution:
    def solve(self, nums, k):
        deq, n, ans = deque([0]), len(nums), []

        for i in range (n):
            if deq[0] <= i - k:
                deq.popleft()
            while deq and nums[i] >= nums[deq[-1]] :
                deq.pop()
            deq.append(i)
            ans.append(nums[deq[0]])
            
        return ans[k-1:]