Sliding Window Maximum

Hard·Tagsarrayqueuesliding-windowmonotonic-queue

Problem Statement

You are given an array of integers `nums`, there is a sliding window of size `k` which is moving from the very left of the array to the very right. You can only see the `k` numbers in the window. Each time the sliding window moves right by one position. Return an array containing the maximum value in the sliding window at each step.

Examples

Example 1

Input

nums: [1, 3, -1, -3, 5, 3, 6, 7], k: 3

Output

"[3, 3, 5, 5, 6, 7]"

Why

Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7

Example 2

Input

nums: [1], k: 1

Output

"[1]"

Why

The window size is 1, so the max is just the element itself.

Constraints

•1 <= nums.length <= 10^5
•-10^4 <= nums[i] <= 10^4
•1 <= k <= nums.length

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

A brute force approach would scan the window of size `k` every time it moves, resulting in O(N * K) time. How can we do this in O(N)?

Hint 2

We need a data structure that allows us to add elements to the back, but also remove old elements from the front as the window slides. A Double-Ended Queue (Deque) is perfect for this.

Hint 3

If a new element is larger than the elements currently in the deque, those smaller elements can NEVER be the maximum in the future. We can safely pop them from the back of the deque!

Hint 4

Store the *indices* of the elements in the deque, not the values. This allows you to easily check if the element at the front of the deque has fallen out of the current window (`index < i - k + 1`).