Dada una array circular arr[] que consta de N enteros, la tarea es imprimir el siguiente elemento mayor para cada elemento de la array circular. Elementos para los que no existe elemento mayor, imprime “-1” .
Ejemplos:
Entrada: arr[] = {5, 6, 7}
Salida: 6 7 -1
Explicación: El siguiente elemento mayor para cada elemento de array es el siguiente:
For arr[0] (= 5) -> 6
For arr[1] (= 6) -> 7
Para arr[2] (= 7), ningún elemento mayor está presente en la array. Por lo tanto, imprima -1.Entrada: arr[] = {4, -2, 5, 3}
Salida: 5 5 -1 4
Explicación: El siguiente elemento mayor para cada elemento de array es el siguiente:
For arr[0] (= 4) -> 5
For arr[1] (= -2) -> 5
Para arr[2] (= 5), ningún elemento mayor está presente en la array. Por lo tanto, imprima -1.
Para arr[3] (= 3) -> 4
Enfoque ingenuo: el enfoque más simple para resolver este problema se analiza en la publicación anterior de este artículo.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque alternativo: consulte la publicación anterior de este artículo para optimizar el espacio del enfoque ingenuo.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar el concepto de Next Greater Element que utiliza una estructura de datos Stack . Siga los pasos a continuación para resolver el problema:
- Inicialice una pila para almacenar los índices de la array y una array nge[] de tamaño N que almacena el siguiente elemento mayor para cada elemento de la array.
- Recorra la array y para cada índice, realice lo siguiente:
- Si la pila no está vacía y el i -ésimo elemento actual de la array es mayor que el elemento superior de la pila , extraiga el elemento superior de la pila y actualice nge[st.top()] almacenando arr[i % N] en eso. Repita esto hasta que la pila esté vacía o el elemento actual sea menor que el elemento en la parte superior de la pila .
- Si la pila está vacía o el elemento actual es menor que la parte superior de la pila, inserte (i % N) en la pila .
- Después de un solo recorrido de N elementos, la pila contiene los elementos que no tienen un siguiente elemento mayor hasta el índice (N – 1) th . Como la array es circular , considere todos los elementos del índice 0 nuevamente y encuentre el siguiente elemento mayor de los elementos restantes.
- Dado que el arreglo se recorre 2 veces , es mejor usar i%N en lugar de i .
- Después de completar los pasos anteriores, imprima la array nge[] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the NGE for the
// given circular array arr[]
void printNGE(int* arr, int n)
{
// Initialize stack and nge[] array
stack<int> s;
int nge[n], i = 0;
// Initialize nge[] array to -1
for (i = 0; i < n; i++) {
nge[i] = -1;
}
i = 0;
// Traverse the array
while (i < 2 * n) {
// If stack is not empty and
// current element is greater
// than top element of the stack
while (!s.empty()
&& arr[i % n] > arr[s.top()]) {
// Assign next greater element
// for the top element of the stack
nge[s.top()] = arr[i % n];
// Pop the top element
// of the stack
s.pop();
}
s.push(i % n);
i++;
}
// Print the nge[] array
for (i = 0; i < n; i++) {
cout << nge[i] << " ";
}
}
// Driver Code
int main()
{
int arr[] = { 4, -2, 5, 8 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
printNGE(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the NGE for the
// given circular array arr[]
static void printNGE(int arr[], int n)
{
// Initialize stack and nge[] array
Stack<Integer> s = new Stack<>();
int nge[] = new int[n];
int i = 0;
// Initialize nge[] array to -1
for(i = 0; i < n; i++)
{
nge[i] = -1;
}
i = 0;
// Traverse the array
while (i < 2 * n)
{
// If stack is not empty and
// current element is greater
// than top element of the stack
while (!s.isEmpty() &&
arr[i % n] > arr[s.peek()])
{
// Assign next greater element
// for the top element of the stack
nge[s.peek()] = arr[i % n];
// Pop the top element
// of the stack
s.pop();
}
s.push(i % n);
i++;
}
// Print the nge[] array
for(i = 0; i < n; i++)
{
System.out.print(nge[i] + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 4, -2, 5, 8 };
int N = arr.length;
// Function Call
printNGE(arr, N);
}
}
// This code is contributed by yashbeersingh42
Python3
# Python3 program for the above approach # Function to find the NGE for the # given circular array arr[] def printNGE(arr, n) : # create stack list s = []; # Initialize nge[] array to -1 nge = [-1] * n; i = 0; # Traverse the array while (i < 2 * n) : # If stack is not empty and # current element is greater # than top element of the stack while (len(s) != 0 and arr[i % n] > arr[s[-1]]) : # Assign next greater element # for the top element of the stack nge[s[-1]] = arr[i % n]; # Pop the top element # of the stack s.pop(); s.append(i % n); i += 1; # Print the nge[] array for i in range(n) : print(nge[i], end= " "); # Driver Code if __name__ == "__main__" : arr = [ 4, -2, 5, 8 ]; N = len(arr); # Function Call printNGE(arr, N); # This code is contributed by AnkitRai01
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the NGE for the
// given circular array []arr
static void printNGE(int []arr, int n)
{
// Initialize stack and nge[] array
Stack<int> s = new Stack<int>();
int []nge = new int[n];
int i = 0;
// Initialize nge[] array to -1
for(i = 0; i < n; i++)
{
nge[i] = -1;
}
i = 0;
// Traverse the array
while (i < 2 * n)
{
// If stack is not empty and
// current element is greater
// than top element of the stack
while (s.Count != 0 &&
arr[i % n] > arr[s.Peek()])
{
// Assign next greater element
// for the top element of the stack
nge[s.Peek()] = arr[i % n];
// Pop the top element
// of the stack
s.Pop();
}
s.Push(i % n);
i++;
}
// Print the nge[] array
for(i = 0; i < n; i++)
{
Console.Write(nge[i] + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 4, -2, 5, 8 };
int N = arr.Length;
// Function Call
printNGE(arr, N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Function to find the NGE for the
// given circular array []arr
function printNGE(arr, n)
{
// Initialize stack and nge[] array
let s = [];
let nge = new Array(n);
let i = 0;
// Initialize nge[] array to -1
for(i = 0; i < n; i++)
{
nge[i] = -1;
}
i = 0;
// Traverse the array
while (i < 2 * n)
{
// If stack is not empty and
// current element is greater
// than top element of the stack
while (s.length != 0 &&
arr[i % n] > arr[s[s.length - 1]])
{
// Assign next greater element
// for the top element of the stack
nge[s[s.length - 1]] = arr[i % n];
// Pop the top element
// of the stack
s.pop();
}
s.push(i % n);
i++;
}
// Print the nge[] array
for(i = 0; i < n; i++)
{
document.write(nge[i] + " ");
}
}
let arr = [ 4, -2, 5, 8 ];
let N = arr.length;
// Function Call
printNGE(arr, N);
// This code is contributed by suresh07.
</script>
Producción:
5 5 8 -1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por yashbeersingh42 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA