Sliding Window Maximum

Lab C++ Advanced 30 points

Read n integers and a window size k. Print the maximum of every window of k consecutive numbers in O(n) using a deque of indexes.

Input

n, the integers, then k.

Output

One line.

Example

Input

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

Output

3 3 5 5 6 7

Sample input available Sample output available

Editor

C++

Hints

Keep indexes of a decreasing sequence; the front is always the window maximum.

Solution explanation

Each index enters and leaves the deque once, so the whole scan is O(n).

Show solution

#include <iostream>
#include <deque>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n;
    vector<int> v(n);
    for (int &x : v) cin >> x;
    cin >> k;
    deque<int> dq;
    bool first = true;
    for (int i = 0; i < n; i++) {
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
        while (!dq.empty() && v[dq.back()] <= v[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) {
            cout << (first ? "" : " ") << v[dq.front()];
            first = false;
        }
    }
    cout << "\n";
    return 0;
}

Output

Answer