Sliding Window Maximum using Deque

Hard STL Containers

Solve in Playground →

Problem Statement

Write a C++ program using `std::deque` to compute the maximum value in every sliding window of size K.

Input Format

First line: N and Window Size K. Second line: N space-separated integers.

Output Format

Print sliding window maximums separated by a space.

Constraints

1 <= K <= N <= 1000

Sample Input

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

Sample Output

3 3 5 5 6 7

Explanation

Monotonic deques maintain sliding window maximums in $O(N)$ time complexity.

Starter Code

#include <iostream>
#include <vector>
#include <deque>

int main() {
    int n, k;
    if (std::cin >> n >> k) {
        // Write your monotonic deque sliding window maximum logic here

    }
    return 0;
}

Limits

Time Limit: 1s
Memory Limit: 256MB

Start Coding in IDE →