Hard

Sliding Window Maximum

096

Given an integer array nums and a window size k, return the maximum value in every contiguous window of k elements as the window moves from left to right.

EXAMPLES

Example 1

Input
{
  "nums": [
    1,
    3,
    -1,
    -3,
    5,
    3,
    6,
    7
  ],
  "k": 3
}

Output
[
  3,
  3,
  5,
  5,
  6,
  7
]

FUNCTION SHAPE

nums: intArrayk: int→intArray

SOLUTION NOTE

Use monotonic deque. Front is always the maximum. Remove elements outside window.

Reveal reference solution +

pythonREFERENCE

def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    n = len(nums)
    dq = deque()
    res = []

    for i in range(n):
        # Maintain monotonically decreasing deque
        while dq and nums[dq[-1]] <= nums[i]:
            dq.pop()
        dq.append(i)

        # Window reached size k
        if i >= k - 1:
            res.append(nums[dq[0]])
            if dq[0] == i - (k - 1):
                dq.popleft()

    return res

TimeO(n)

SpaceO(k)

Open on LeetCode ↗