Sliding Window Maximum

Given an array of integers nums and an integer k representing the size of a sliding window, the window moves from the very left to the very right of the array. Each time the window moves one position to the right, return the maximum value in the current window.

Return an array of the maximum values for each window position.

Examples

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

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

Explanation:

• Window [1,3,-1] → max = 3
• Window [3,-1,-3] → max = 3
• Window [-1,-3,5] → max = 5
• Window [-3,5,3] → max = 5
• Window [5,3,6] → max = 6
• Window [3,6,7] → max = 7

Input: nums = [1], k = 1

Output: [1]

Explanation: Only one window of size 1, which contains just the element 1.

Input: nums = [1,-1], k = 1

Output: [1,-1]

Explanation: Each element is its own window of size 1.

Constraints

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