Dada una array, imprima el siguiente elemento mayor (NGE) para cada elemento. El siguiente elemento mayor para un elemento x es el primer elemento mayor en el lado derecho de x en la array. Elementos para los que no existe un elemento mayor, considere el siguiente elemento mayor como -1.
Ejemplos:
- Para una array, el elemento más a la derecha siempre tiene el siguiente elemento mayor como -1.
- Para una array ordenada en orden decreciente, todos los elementos tienen el siguiente elemento mayor como -1.
- Para la array de entrada [4, 5, 2, 25], los siguientes elementos mayores para cada elemento son los siguientes.
Element NGE 4 --> 5 5 --> 25 2 --> 25 25 --> -1
d) Para la array de entrada [13, 7, 6, 12}, los siguientes elementos mayores para cada elemento son los siguientes.
Element NGE 13 --> -1 7 --> 12 6 --> 12 12 --> -1
Método 1 (Simple)
Use dos bucles: El bucle exterior recoge todos los elementos uno por uno. El bucle interior busca el primer elemento mayor para el elemento elegido por el bucle exterior. Si se encuentra un elemento mayor, ese elemento se imprime como el siguiente; de lo contrario, se imprime -1.
A continuación se muestra la implementación del enfoque anterior:
C++
// Simple C++ program to print
// next greater elements in a
// given array
#include<iostream>
using namespace std;
/* prints element and NGE pair
for all elements of arr[] of size n */
void printNGE(int arr[], int n)
{
int next, i, j;
for (i = 0; i < n; i++)
{
next = -1;
for (j = i + 1; j < n; j++)
{
if (arr[i] < arr[j])
{
next = arr[j];
break;
}
}
cout << arr[i] << " -- "
<< next << endl;
}
}
// Driver Code
int main()
{
int arr[] = {11, 13, 21, 3};
int n = sizeof(arr)/sizeof(arr[0]);
printNGE(arr, n);
return 0;
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
11 -- 13 13 -- 21 21 -- -1 3 -- -1
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Método 2 (usando la pila)
- Empuje el primer elemento para apilar.
- Elija el resto de los elementos uno por uno y siga los siguientes pasos en bucle.
- Marca el elemento actual como siguiente .
- Si la pila no está vacía, compare el elemento superior de la pila con el siguiente .
- Si el siguiente es mayor que el elemento superior, extrae el elemento de la pila. next es el siguiente elemento mayor para el elemento reventado.
- Siga sacando de la pila mientras el elemento sacado es más pequeño que el siguiente . next se convierte en el siguiente elemento mayor para todos esos elementos reventados.
- Finalmente, empuje el siguiente en la pila.
- Después de que termine el bucle en el paso 2, extraiga todos los elementos de la pila e imprima -1 como el siguiente elemento para ellos.
La imagen de abajo es una ejecución en seco del enfoque anterior:
A continuación se muestra la implementación del enfoque anterior:
C++
// A Stack based C++ program to find next
// greater element for all array elements.
#include <bits/stdc++.h>
using namespace std;
/* prints element and NGE pair for all
elements of arr[] of size n */
void printNGE(int arr[], int n)
{
stack<int> s;
/* push the first element to stack */
s.push(arr[0]);
// iterate for rest of the elements
for (int i = 1; i < n; i++)
{
if (s.empty()) {
s.push(arr[i]);
continue;
}
/* if stack is not empty, then
pop an element from stack.
If the popped element is smaller
than next, then
a) print the pair
b) keep popping while elements are
smaller and stack is not empty */
while (s.empty() == false
&& s.top() < arr[i])
{
cout << s.top()
<< " --> " << arr[i] << endl;
s.pop();
}
/* push next to stack so that we can find
next greater for it */
s.push(arr[i]);
}
/* After iterating over the loop, the remaining
elements in stack do not have the next greater
element, so print -1 for them */
while (s.empty() == false) {
cout << s.top() << " --> " << -1 << endl;
s.pop();
}
}
/* Driver code */
int main()
{
int arr[] = { 11, 13, 21, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
printNGE(arr, n);
return 0;
}
11 --> 13 13 --> 21 3 --> -1 21 --> -1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
El peor caso ocurre cuando todos los elementos se ordenan en orden decreciente. Si los elementos se ordenan en orden decreciente, cada elemento se procesa como máximo 4 veces.
- Inicialmente empujado a la pila.
- Se extrae de la pila cuando se procesa el siguiente elemento.
- Empujado de nuevo a la pila porque el siguiente elemento es más pequeño.
- Extraído de la pila en el paso 3 del algoritmo.
¿Cómo obtener elementos en el mismo orden que la entrada?
El enfoque anterior puede no producir elementos de salida en el mismo orden que la entrada. Para lograr el mismo orden, podemos recorrer el mismo en orden inverso
A continuación se muestra la implementación del enfoque anterior:
C++
// A Stack based C++ program to find next
// greater element for all array elements
// in same order as input.
#include <bits/stdc++.h>
using namespace std;
/* prints element and res pair for all
elements of arr[] of size n */
void printNGE(int arr[], int n)
{
stack<int> s;
int res[n];
for (int i = n - 1; i >= 0; i--) {
/* if stack is not empty, then
pop an element from stack.
If the popped element is smaller
than next, then
a) print the pair
b) keep popping while elements are
smaller and stack is not empty */
if (!s.empty()) {
while (!s.empty() && s.top() <= arr[i]) {
s.pop();
}
}
res[i] = s.empty() ? -1 : s.top();
s.push(arr[i]);
}
for (int i = 0; i < n; i++)
cout << arr[i] << " --> " << res[i] << endl;
}
// Driver Code
int main()
{
int arr[] = { 11, 13, 21, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
printNGE(arr, n);
return 0;
}
11 ---> 13 13 ---> 21 21 ---> -1 3 ---> -1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Consulte para obtener una solución optimizada para imprimir en el mismo orden.
¡ Consulte el artículo completo sobre el próximo elemento mayor para obtener más detalles!
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