Given an array nums and a window size k, slide a window of length k from left to right one position at a time, starting with the first k elements. For each window position, record the maximum value inside the window. Return the array of window maxima.
Input
nums: an array of integers
k: positive window size, k <= nums.length
Output
An array of length nums.length - k + 1 with the maximum of each window.
Examples
Example 1
Inputnums = [1, 2, 3, 4, 5], k = 3
Output[3, 4, 5]
Example 2
Inputnums = [3, 1, 4, 1, 5, 9], k = 1
Output[3, 1, 4, 1, 5, 9]
Constraints
1 <= k <= nums.length
Solve in O(n) time.