Sliding Window Maximum

Given an array of n integers and a sliding window of size k, your task is to compute the maximum value in each window as it moves from the beginning to the end of the array.

For each window starting from index \(i\) to \(i+k-1\), the maximum element is defined as:

\(\max_{j=i}^{i+k-1}\, \text{nums}[j]\)

An efficient approach uses a double‐ended queue (deque) to keep potential candidates for the maximum, achieving a time complexity of \(O(n)\). Use this technique to solve the problem.

inputFormat

The input is given via standard input (stdin) and has the following format:

1. The first line contains two integers n and k separated by a space, where n is the number of elements in the array and k is the size of the sliding window.
2. The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output a single line to stdout containing n-k+1 space-separated integers. Each integer represents the maximum value within each sliding window of the array.

8 3
1 3 -1 -3 5 3 6 7

3 3 5 5 6 7