In this HackerRank Deque-STL problem in c++, we have given a set of arrays of size N and an integer K, you have to find the maximum integer for each and every contiguous subarray of size K for each of the given arrays.

HackerRank Deque-STL in C++ problem solution

 

HackerRank Deque-STL in C++ problem solution

//#pragma comment(linker, "/STACK:640000000")

#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <list>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <bitset>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define forn1(i, n) for(int i = 1; i <= (int)(n); i++)
#define forr(i, l, r) for(int i = int(l); i <= int(r); i++)
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)((a).size())
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define y1 __y1
#define sqr(x) ((x) * (x))
 
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
 
const int INF = (int)(1e9);
const li INF64 = (li)(INF) * (li)(INF);
const ld eps = 1e-9;
const ld pi = ld(3.1415926535897932384626433832795);
 
inline bool in(int i, int j, int n, int m) {
    return i >= 1 && i <= n && j >= 1 && j <= m;
}
 
inline int myrand() {
    return (rand() ^ (rand() << 15));
}
 
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
 
const int N = 5e4 + 555;

int n, k, a[N];

inline void gen() {
    return;
}

inline bool read() {
	if(scanf("%d %d", &n, &k) != 2) return false;
	forn1(i, n) assert(scanf("%d", &a[i]) == 1);
    return true;
}

struct minQueue {
	stack<pt> s1, s2;
	minQueue() {}

	void push(int x) {
		int mx = s1.empty() ? x : max(x, s1.top().y);
		s1.push(mp(x, mx));
	}

	void pop() {
		if(s2.empty()) {
			while(!s1.empty()) {
				int mx = s1.top().x;
				if(!s2.empty()) mx = max(mx, s2.top().y);
				s2.push(mp(s1.top().x, mx));
				s1.pop();
			}
		}

		s2.pop();
	}

	int getMax() {
		if(s1.empty()) return s2.top().y;
		if(s2.empty()) return s1.top().y;
		return max(s1.top().y, s2.top().y);
	}
};

inline void solve() {
	minQueue q;
	forn1(i, k - 1) q.push(a[i]);
	for(int i = k; i <= n; i++) {
		q.push(a[i]);
		printf("%d ", q.getMax());
		q.pop();
	}
	puts("");
    return;
}
 
int main() {
#ifdef _DEBUG
    assert(freopen("input.txt", "rt", stdin));
    assert(freopen("output.txt", "wt", stdout));
#endif
 
    cout << setprecision(10) << fixed;
    cerr << setprecision(10) << fixed;
 
    srand(int(time(NULL)));

    int T = 1;
    assert(scanf("%d", &T) == 1);

	forn(i, T) {
        //cerr << "TEST == " << i + 1 << endl;
        assert(read());
        solve();
    }
 
#ifdef _DEBUG
    cerr << "TIME == " << clock() << " ms" << endl;
#endif
    return 0;
}