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

There are a big variety of different algorithms for this problem. The most difficult, but most efficient uses idea of decreasing deque: on each moment of time we will keep only decreasing numbers in it. Let us consider the following example: nums = [1,3,-1,-3,5,3,6,7], k = 3. Let us process numbers one by one: (I will print numbers, however we will keep indexes in our stack):

  1. We put 1 into emtpy deque: [1].
  2. New element is bigger, than previous, so we remove previous element and put new one: [3].
  3. Next element is smaller than previous, put it to the end of deque: [3, -1].
  4. Similar to previous step: [3, -1, -3].
  5. Now, let us look at the first element 3, it has index 1 in our data, what does it mean? It was to far ago, and we need to delete it: so we popleft it. So, now we have [-1, -3]. Then we check that new element is bigger than the top of our deque, so we remove two elements and have [5] in the end.
  6. New element is smaller than previous, just add it to the end: [5, 3].
  7. New element is bigger, remove elements from end, until we can put it: [6].
  8. New element is bigger, remove elements from end, until we can put it: [7].

So, once again we have the following rules:

  1. Elements in deque are always in decreasing order.
  2. They are always elements from last sliding window of k elements.
  3. It follows from here, that biggest element in current sliding window will be the 0-th element in it.

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.

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

        for i in range (n):
            while deq and 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:]

If you like the solution, you can upvote it on leetcode discussion section: Problem 0239