Sliding Window Maximum
HardSliding Window
You are given an integer array nums and a window size k. Place a window over the first k elements, then slide it right one position at a time until it covers the last k elements. That gives nums.length - k + 1 windows.
Return a list with the maximum value of each window, in order from the leftmost window to the rightmost.
Example 1
- Input:
- nums = [4, 2, 12, 3, 8, 1, 5], k = 3
- Output:
- [12, 12, 12, 8, 8]
- Explanation
- The windows are [4, 2, 12], [2, 12, 3], [12, 3, 8], [3, 8, 1] and [8, 1, 5]. 12 is the maximum while it is inside the window, then 8 takes over once 12 slides out.
Example 2
- Input:
- nums = [9, 8, 7, 6], k = 2
- Output:
- [9, 8, 7]
- Explanation
- Each maximum leaves as soon as the window moves past it, so the answer steps down: 9, 8, 7.
Example 3
- Input:
- nums = [2, 1, 3], k = 1
- Output:
- [2, 1, 3]
- Explanation
- With a window of size 1 every element is its own maximum, so the output equals the input.
Constraints
- 1 ≤
nums.length≤ 105 - -104 ≤
nums[i]≤ 104 - 1 ≤
k≤nums.length