< Back




239. Sliding Window Maximum

This is a Hard problem, and I can see why. We're given an integer array and asked to return another
array of the maximum value encountered in each sliding window of size k. The best way to solve this
involves a monotonic stack wherein we maintain the indices of the maximum values found within each
sliding window.

Before adding a value to the stack, we pop off any values that are less than the current value. This
maintains the maximization nature of our monotonic stack. We add the index of the new value to the
stack.

We check to see if the sum of the window size, k, and the index of the greatest element, at the end
of the stack, is equal to the current index. This tells us that the window has grown too large,
past k, therefore we pop the leftmost index off the stack.

Finally, if the size of the window is greater than or equal to k, we add the value at the leftmost
index, the maximal value of this current sliding window, to the answer array.

The solution is as follows:


  from collections import deque

  class Solution:
      def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
          ans = []
          queue = deque()
          for i in range(len(nums)):
              while queue and nums[i] > nums[queue[-1]]:
                  queue.pop()

              queue.append(i)

              if queue[0] + k == i:
                  queue.popleft()

              if i >= k - 1:
                  ans.append(nums[queue[0]])

          return ans


_ Time Complexity:

  O(n) - We process all integers in the input list once.

_ Space Complexity:

  O(k) - We store at most k values in the monotonic stack.