Sliding Window Maximum

hard

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 the max value for each window position.

Test Cases

Copy an input into the main harness and Run to verify

Input

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

Expected Output

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

Explanation: Window positions: [1 3 -1] -3 5 3 6 7 -> 3, then 1 [3 -1 -3] 5 3 6 7 -> 3, and so on.

Input

nums = [1], k = 1

Expected Output

[1]

Constraints

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

Hints

Hint 1 — click to reveal

A plain queue is not enough — you need a monotonic deque of candidate maxima.

Hint 2 — click to reveal

Drop smaller elements from the back; drop expired indices from the front.

Java Compiler