Queries with Fixed Length

Consider an -integer sequence, . We perform a query by using an integer,d, to calculate the result of the following expression:
In other words, if we let, then you need to calculate.
Given arr and q queries, return a list of answers to each query.

Example:

Input:  n=5,m=5,arr[]={33,11,44,11,55},queries={1,2,3,4,5}
Output: 11
33
44
44
55

Approach

Java

import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class QueriesFixedLength {
    public static void main(String[] args) {
        int[] arr = { 33, 11, 44, 11, 55 };
        int[] queries = { 1, 2, 3, 4, 5 };
        int[] res = solve(arr, queries);
        System.out.println(Arrays.toString(res));
    }

    private static int[] solve(int[] arr, int[] queries) {
        List<Integer> res = new Stack<Integer>();
        int n = arr.length;
        for (int j = 0; j < queries.length; j++) {
            int d = queries[j];

            Stack<int[]> st1 = new Stack<int[]>();
            Stack<int[]> st2 = new Stack<int[]>();

            for (int i = 0; i < d; i++) {
                add(arr[i], st1, st2);
            }
            int ans = max_elem(st1, st2);
            for (int i = d; i < n; i++) {
                remove(st1, st2);
                add(arr[i], st1, st2);
                ans = Math.min(max_elem(st1, st2), ans);
            }
            res.add(ans);
        }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }

    static int max_elem(Stack<int[]> st1, Stack<int[]> st2) {
        if (st1.isEmpty() || st2.isEmpty()) {
            if (st1.isEmpty())
                return st2.peek()[1];
            return st1.peek()[1];
        }
        return Math.max(st1.peek()[1], st2.peek()[1]);
    }

    static void add(int new_elem, Stack<int[]> st1, Stack<int[]> st2) {
        int max1;
        if (st1.isEmpty())
            max1 = new_elem;
        else
            max1 = Math.max(new_elem, st1.peek()[1]);
        st1.add(new int[] { new_elem, max1 });
    }

    static void remove(Stack<int[]> st1, Stack<int[]> st2) {
        if (st2.isEmpty()) {
            while (!st1.isEmpty()) {
                int element = st1.pop()[0];
                int max1;
                if (st2.isEmpty())
                    max1 = element;
                else
                    max1 = Math.max(element, st2.peek()[1]);
                st2.add(new int[] { element, max1 });
            }
        }
        st2.pop();
    }

}

C++

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

int max_elem(stack<pair<int, int>> &st1, stack<pair<int, int>> &st2)
{
    if (st1.empty() || st2.empty())
    {
        if (st1.empty())
            return st2.top().second;
        return st1.top().second;
    }
    return max(st1.top().second, st2.top().second);
}
void add(int new_elem, stack<pair<int, int>> &st1, stack<pair<int, int>> &st2)
{
    int max1;
    if (st1.empty())
        max1 = new_elem;
    else
        max1 = max(new_elem, st1.top().second);
    st1.push({new_elem, 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;
            if (st2.empty())
                max1 = element;
            else
                max1 = max(element, st2.top().second);
            st2.push({element, max1});
        }
    }
    st2.pop();
}
vector<int> solve(vector<int> arr, vector<int> queries)
{
    vector<int> res;
    int n = arr.size();
    for (int j = 0; j < queries.size(); j++)
    {
        int d = queries[j];

        stack<pair<int, int>> st1, st2;
        for (int i = 0; i < d; i++)
            add(arr[i], st1, st2);
        int ans = max_elem(st1, st2);
        for (int i = d; i < n; i++)
        {
            remove(st1, st2);
            add(arr[i], st1, st2);
            ans = min(max_elem(st1, st2), ans);
        }
        res.push_back(ans);
    }
    return res;
}
int main()
{
    int n = 5, m = 5;
    vector<int> arr = {33, 11, 44, 11, 55};
    vector<int> queries = {1, 2, 3, 4, 5};
    vector<int> res = solve(arr, queries);
    for (int i = 0; i < res.size(); i++)
    {
        cout << res[i] << "\n";
    }
    return 0;
}