Deque-STL

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.

Example:

Input: n = 5, k = 2, arr[n] = {3, 4, 6, 3, 4}
Output: 4 6 6 4 

Approach

C++

#include <bits/stdc++.h>
using namespace std;

void add(stack<pair<int, int>> &st1, int new_elem)
{
    if (st1.empty())
        st1.push({new_elem, new_elem});
    else
        st1.push({new_elem, max(new_elem, st1.top().second)});
}
int get_max(stack<pair<int, int>> &st1,
       stack<pair<int, int>> &st2)
{
    int max1;
    if (st1.empty() || st2.empty())
        max1 = st1.empty() ? st2.top().second : st1.top().second;
    else
        max1 = max(st1.top().second, st2.top().second);
    return max1;
}
void remove(stack<pair<int, int>> &st1, 
       stack<pair<int, int>> &st2)
{
    if (st2.empty())
    {
        while (!st1.empty())
        {
            int element = st1.top().first;
            st1.pop();
            int max1 = st2.empty() ? element :
               max(st2.top().second, element);
            st2.push({element, max1});
        }
    }
    st2.pop();
}
void printKMax(int arr[], int n, int k)
{

    stack<pair<int, int>> st1, st2;
    for (int i = 0; i < k; i++)
        add(st1, arr[i]);
    cout << get_max(st1, st2) << " ";
    for (int i = k; i < n; i++)
    {

        remove(st1, st2);
        add(st1, arr[i]);
        cout << get_max(st1, st2) << " ";
    }
    cout << "\n";
}

int main()
{

    int n = 5, k = 2;

    int arr[n] = {3, 4, 6, 3, 4};

    printKMax(arr, n, k);

    return 0;
}