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 = 5Salida: 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; }
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