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. Los siguientes elementos mayores deben imprimirse en el mismo orden que la array de entrada.
Ejemplos:
Entrada: arr[] = [4, 5, 2, 25}
Salida: 5 25 25 -1Entrada: arr[] = [4, 5, 2, 25, 10}
Salida: 5 25 25 -1 -1
Hemos discutido una solución aquí que no imprime el mismo orden. Aquí recorremos la array desde el elemento más a la derecha.
- En este enfoque, hemos comenzado a iterar desde el último elemento (nth) hasta el primer (1st) elemento.
El beneficio es que cuando lleguemos a un cierto índice, su próximo elemento mayor ya estará en la pila, y podemos obtener directamente este elemento mientras en el mismo índice. - Después de alcanzar un cierto índice, abriremos la pila hasta que obtengamos el elemento mayor en la parte superior del elemento actual y ese elemento será la respuesta para el elemento actual.
- Si la pila se vacía mientras se realiza la operación emergente, la respuesta sería -1
. Luego, almacenaremos la respuesta en una array para el índice actual.
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 NGE pair for all
elements of arr[] of size n */
void printNGE(int arr[], int n)
{
stack<int> s;
int arr1[n];
// iterating from n-1 to 0
for (int i = n - 1; i >= 0; i--)
{
/*We will pop till we get the
greater element on top or stack gets empty*/
while (!s.empty() && s.top() <= arr[i])
s.pop();
/*if stack gots empty means there
is no element on right which is greater
than the current element.
if not empty then the next greater
element is on top of stack*/
if (s.empty())
arr1[i] = -1;
else
arr1[i] = s.top();
s.push(arr[i]);
}
for (int i = 0; i < n; i++)
cout << arr[i] << " ---> " << arr1[i] << endl;
}
/* Driver program to test above functions */
int main()
{
int arr[] = { 11, 13, 21, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
printNGE(arr, n);
return 0;
}
Java
// A Stack based Java program to find next
// greater element for all array elements
// in same order as input.
import java.util.*;
class GfG {
/* prints element and NGE pair for all
elements of arr[] of size n */
static void printNGE(int arr[], int n)
{
Stack<Integer> s = new Stack<Integer>();
int arr1[] = new int[n];
// iterating from n-1 to 0
for (int i = n - 1; i >= 0; i--)
{
/*We will pop till we get the
greater element on top or stack gets empty*/
while (!s.isEmpty() && s.peek() <= arr[i])
s.pop();
/*if stack gots empty means there
is no element on right which is greater
than the current element.
if not empty then the next greater
element is on top of stack*/
if (s.empty())
arr1[i] = -1;
else
arr1[i] = s.peek();
s.push(arr[i]);
}
for (int i = 0; i < n; i++)
System.out.println(arr[i] + " ---> " + arr1[i]);
}
/* Driver program to test above functions */
public static void main(String[] args)
{
int arr[] = { 11, 13, 21, 3 };
int n = arr.length;
printNGE(arr, n);
}
}
Python3
# A Stack based Python3 program to find next # greater element for all array elements # in same order as input. # prints element and NGE pair for all # elements of arr[] of size n def printNGE(arr, n): s = list() arr1 = [0 for i in range(n)] # iterating from n-1 to 0 for i in range(n - 1, -1, -1): # We will pop till we get the greater # element on top or stack gets empty while (len(s) > 0 and s[-1] <= arr[i]): s.pop() # if stack gots empty means there # is no element on right which is # greater than the current element. # if not empty then the next greater # element is on top of stack if (len(s) == 0): arr1[i] = -1 else: arr1[i] = s[-1] s.append(arr[i]) for i in range(n): print(arr[i], " ---> ", arr1[i] ) # Driver Code arr = [ 11, 13, 21, 3 ] n = len(arr) printNGE(arr, n) # This code is contributed by Mohit kumar 29
C#
// A Stack based C# program to find next
// greater element for all array elements
// in same order as input.
using System;
using System.Collections.Generic;
class GFG
{
/* prints element and NGE pair for all
elements of arr[] of size n */
static void printNGE(int []arr, int n)
{
Stack<int> s = new Stack<int>();
int []arr1 = new int[n];
// iterating from n-1 to 0
for (int i = n - 1; i >= 0; i--)
{
/*We will pop till we get the
greater element on top or stack gets empty*/
while (s.Count != 0 && s.Peek() <= arr[i])
s.Pop();
/*if stack gots empty means there
is no element on right which is greater
than the current element.
if not empty then the next greater
element is on top of stack*/
if (s.Count == 0)
arr1[i] = -1;
else
arr1[i] = s.Peek();
s.Push(arr[i]);
}
for (int i = 0; i < n; i++)
Console.WriteLine(arr[i] + " ---> " +
arr1[i]);
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 11, 13, 21, 3 };
int n = arr.Length;
printNGE(arr, n);
}
}
// This code is contributed by Ajay Kumar
Javascript
<script>
// A Stack based Javascript program to find next
// greater element for all array elements
// in same order as input.
// prints element and NGE pair for all
// elements of arr[] of size n
function printNGE(arr, n)
{
let s = [];
let arr1 = new Array(n);
// Iterating from n-1 to 0
for (let i = n - 1; i >= 0; i--)
{
// We will pop till we get the
// greater element on top or
// stack gets empty
while (!s.length == 0 &&
s[s.length - 1] <= arr[i])
s.pop();
// If stack gots empty means there
// is no element on right which is greater
// than the current element.
// if not empty then the next greater
// element is on top of stack
if (s.length == 0)
arr1[i] = -1;
else
arr1[i] = s[s.length - 1];
s.push(arr[i]);
}
for(let i = 0; i < n; i++)
document.write(arr[i] + " ---> " +
arr1[i] + "<br>");
}
// Driver code
let arr = [ 11, 13, 21, 3 ];
let n = arr.length;
printNGE(arr, n);
// This code is contributed by patel2127
</script>
Producción :
11 -- 13 13 -- 21 21 -- -1 3 -- -1
Complejidad de tiempo: O(n)
Espacio auxiliar: O(n) No se requiere espacio adicional si desea imprimir el siguiente mayor de cada elemento en orden inverso al de entrada (significa primero, para el último elemento y luego para el penúltimo y así sucesivamente hasta el primer elemento)