Número de NGE a la derecha

Dada una array de N enteros y Q consultas, imprima el número de los siguientes elementos mayores a la derecha del elemento de índice dado. 
Ejemplos: 

Entrada: a[] = {3, 4, 2, 7, 5, 8, 10, 6} 
q = 2 
índice = 0, índice = 5

Salida: 6, 1 
Explicación: Los siguientes elementos mayores a la derecha de 3 (índice 0) son 4,7,5,8,10,6. 
Los siguientes elementos mayores a la derecha de 8 (índice 5) son 10.

Enfoque ingenuo: para resolver el problema, siga la siguiente idea:

Itere para cada consulta desde el índice hasta el final y descubra la cantidad de elementos siguientes más grandes a la derecha

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ code for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find number of next
// greater elements on the right of
// a given element
int nextGreaterElements(vector<int>& a, int index)
{
    int count = 0, N = a.size();
    for (int i = index + 1; i < N; i++)
        if (a[i] > a[index])
            count++;
 
    return count;
}
 
// Driver's code
int main()
{
 
    vector<int> a = { 3, 4, 2, 7, 5, 8, 10, 6 };
    int Q = 2;
    vector<int> queries = { 0, 5 };
 
    for (int i = 0; i < Q; i++)
        // Function call
        cout << nextGreaterElements(a, queries[i]) << " ";
 
    return 0;
}
Producción

6 1 

Complejidad de tiempo: O(NQ) y O(N) para responder una sola consulta
Espacio auxiliar: O(1) 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *