Sliding Window Maximum

Problem Given an array nums and a window size k, return the maximum of each contiguous window as it slides from left to right.

Input / Output

• Input: int array nums, int k.
• Output: an array of n-k+1 window maxima.

Constraints

• 1 <= k <= n <= 10^5 — the O(n*k) brute force is too slow; O(n) is expected.

Example

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