193. Sliding Window Maximum
Challenge1000 ms256 MBSolved by 0%
Print the largest value in every window of k consecutive elements.
For [1, 3, -1, -3, 5, 3, 6, 7] with k = 3 the answers are 3 3 5 5 6 7.
This is the classic queue question, and it is the previous problem with the removals driven by the window rather than by an operation list.
Constraints - `1 ≤ k ≤ n ≤ 200000` - `-1000000000 ≤ value ≤ 1000000000`
Input
The first line contains two integers n and k.
The second line contains n space-separated integers.
Output
Print n - k + 1 integers on ONE line, separated by single spaces, the maximum of each window, left to right.
Input8 3
1 3 -1 -3 5 3 6 7
Output3 3 5 5 6 7
Noteis the worked example from the statement
Input1 1
7
Output7
Noteis a single element with a window of one
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.