Sliding Window Maximum

You are given an array of n integers and an integer k. A window of size k slides from the very left of the array to the very right, moving one position at a time. For each position of the window, report the maximum value contained within it.

Input: The first line contains two space-separated integers n and k. The second line contains n space-separated integers representing the array. Output: Print n - k + 1 space-separated integers on a single line: the maximum value of each window, in the order the windows appear.

1 <= k <= n <= 10^5 -10^4 <= arr[i] <= 10^4

This is the SAME monotonic-deque technique as the identically-purposed Queue-category problem - a strong reminder that the exact same algorithm can appear filed under different category names across a large problem bank.

For every fixed-size window sliding across an array, find its maximum value efficiently. Brute force: For every window position, scan all k elements directly to find the maximum - this costs O(n*k), too slow for large n and k. Optimised: Maintaining the deque in strictly decreasing value order means the FRONT is always the current maximum candidate, and popping stale/beaten values from either end ensures every element is pushed and popped from the deque AT MOST ONCE across the whole algorithm, giving true O(n) total work.

1. Maintain a DEQUE of indices whose corresponding VALUES are in STRICTLY DECREASING order from front to back. 2. Before adding a new index, remove indices from the BACK whose values are <= the new value - they can never be the maximum again while the new value remains in range. 3. Remove the index at the FRONT whenever it slides outside the current window; the front of the deque always holds the current window's maximum.

Time: O(n) - each element enters and leaves the deque at most once. Space: O(k) in the worst case, for the deque holding at most k candidate indices.

Handle k = 1 (the output is simply the array itself) and k = n (a single output value, the maximum of the whole array). An O(n log n) or worse approach may not run in time for n at its upper bound, so an O(n) technique is expected.

Be ready to explain both pruning rules clearly: popping from the back when a new value beats older candidates, and popping from the front when a candidate slides out of the window's range.