ArraySliding WindowMonotonic Deque
A window of size k slides from the left of the array to the right, one position at a time. Report the maximum value inside the window at each position.
Input
Line 1: n and k. Line 2: n integers.
Output
Print n - k + 1 values: the maximum of each window, separated by spaces.
Constraints
1 <= k <= n <= 10^5 -10^4 <= each value <= 10^4
Example 1
Input
8 3 1 3 -1 -3 5 3 6 7
Output
3 3 5 5 6 7
Windows [1 3 -1], [3 -1 -3], [-1 -3 5] and so on give maxima 3 3 5 5 6 7.