Elemento mayor siguiente

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: 

  1. Para una array, el elemento más a la derecha siempre tiene el siguiente elemento mayor como -1.
  2. Para una array ordenada en orden decreciente, todos los elementos tienen el siguiente elemento mayor como -1.
  3. 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.

Complete Interview Preparation - GFG

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)

C

       
// Simple C program to print next greater elements
// in a given array
#include<stdio.h>
  
/* 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;
            }
        }
        printf("%d -- %dn", arr[i], next);
    }
}
  
int main()
{
    int arr[]= {11, 13, 21, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    printNGE(arr, n);
    return 0;
}

Java

// Simple Java program to print next 
// greater elements in a given array
  
class Main
{ 
    /* prints element and NGE pair for 
     all elements of arr[] of size n */
    static 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;
                }
            }
            System.out.println(arr[i]+" -- "+next);
        }
    }
       
    public static void main(String args[])
    {
        int arr[]= {11, 13, 21, 3};
        int n = arr.length;
        printNGE(arr, n);
    }
}

Python

   
# Function to print element and NGE pair for all elements of list
def printNGE(arr):
  
    for i in range(0, len(arr), 1):
  
        next = -1
        for j in range(i+1, len(arr), 1):
            if arr[i] < arr[j]:
                next = arr[j]
                break
              
        print(str(arr[i]) + " -- " + str(next))
  
# Driver program to test above function
arr = [11,13,21,3]
printNGE(arr)
  
# This code is contributed by Sunny Karira

C#

// Simple C# program to print next 
// greater elements in a given array
using System;
  
class GFG
{
      
    /* prints element and NGE pair for 
    all elements of arr[] of size n */
    static 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;
                }
            }
            Console.WriteLine(arr[i] + " -- " + next);
        }
    }
      
    // driver code
    public static void Main()
    {
        int []arr= {11, 13, 21, 3};
        int n = arr.Length;
          
        printNGE(arr, n);
    }
}
  
// This code is contributed by Sam007

PHP

<?php
// Simple PHP program to print next
// greater elements in a given array
  
/* prints element and NGE pair for 
   all elements of arr[] of size n */
function printNGE($arr, $n)
{
    for ($i = 0; $i < $n; $i++)
    {
        $next = -1;
        for ($j = $i + 1; $j < $n; $j++)
        {
            if ($arr[$i] < $arr[$j])
            {
                $next = $arr[$j];
                break;
            }
        }
        echo $arr[$i]." -- ". $next."\n";
          
    }
}
  
    // Driver Code
    $arr= array(11, 13, 21, 3);
    $n = count($arr);
    printNGE($arr, $n);
      
// This code is contributed by Sam007
?>

Javascript

<script>
      // Simple JavaScript program to print
      // next greater elements in a
      // given array
  
      /* prints element and NGE pair
      for all elements of arr[] of size n */
      function printNGE(arr, n)
      {
        var 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;
            }
          }
          document.write(arr[i] + " -- " + next);
          document.write("<br>");
        }
      }
  
      // Driver Code
      var arr = [11, 13, 21, 3];
      var n = arr.length;
      printNGE(arr, n);
        
      // This code is contributed by rdtank.
    </script>
Producción

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. 
    1. Marca el elemento actual como siguiente .
    2. Si la pila no está vacía, compare el elemento superior de la pila con el siguiente .
    3. 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.
    4. 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;
}

C

// A Stack based C program to find next 
//  greater element for all array elements.
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#define STACKSIZE 100
  
// stack structure
struct stack {
    int top;
    int items[STACKSIZE];
};
  
// Stack Functions to be used by printNGE()
void push(struct stack* ps, int x)
{
    if (ps->top == STACKSIZE - 1) {
        printf("Error: stack overflown");
        getchar();
        exit(0);
    }
    else {
        ps->top += 1;
        int top = ps->top;
        ps->items[top] = x;
    }
}
  
bool isEmpty(struct stack* ps)
{
    return (ps->top == -1) ? true : false;
}
  
int pop(struct stack* ps)
{
    int temp;
    if (ps->top == -1) {
        printf("Error: stack underflow n");
        getchar();
        exit(0);
    }
    else {
        int top = ps->top;
        temp = ps->items[top];
        ps->top -= 1;
        return temp;
    }
}
  
/* prints element and NGE pair for all elements of
arr[] of size n */
void printNGE(int arr[], int n)
{
    int i = 0;
    struct stack s;
    s.top = -1;
    int element, next;
  
    /* push the first element to stack */
    push(&s, arr[0]);
  
    // iterate for rest of the elements
    for (i = 1; i < n; i++) {
        next = arr[i];
  
        if (isEmpty(&s) == false)
        {
            // if stack is not empty, then pop an element
            // from stack
            element = pop(&s);
  
            /* 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 (element < next) {
                printf("n %d --> %d", element, next);
                if (isEmpty(&s) == true)
                    break;
                element = pop(&s);
            }
  
            /* If element is greater than next, then push
               the element back */
            if (element > next)
                push(&s, element);
        }
  
        /* push next to stack so that we can find
           next greater for it */
        push(&s, next);
    }
  
    /* After iterating over the loop, the remaining
       elements in stack do not have the next greater
       element, so print -1 for them */
    while (isEmpty(&s) == false)
    {
        element = pop(&s);
        next = -1;
        printf("n %d --> %d", element, next);
    }
}
  
/* Driver code */
int main()
{
    int arr[] = { 11, 13, 21, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printNGE(arr, n);
    getchar();
    return 0;
}

Java

// Java program to print next
// greater element using stack
  
public class NGE {
    static class stack {
        int top;
        int items[] = new int[100];
  
        // Stack functions to be used by printNGE
        void push(int x)
        {
            if (top == 99) 
            {
                System.out.println("Stack full");
            }
            else
            {
                items[++top] = x;
            }
        }
  
        int pop()
        {
            if (top == -1) 
            {
                System.out.println("Underflow error");
                return -1;
            }
            else {
                int element = items[top];
                top--;
                return element;
            }
        }
  
        boolean isEmpty()
        {
            return (top == -1) ? true : false;
        }
    }
  
    /* prints element and NGE pair for
       all elements of arr[] of size n */
    static void printNGE(int arr[], int n)
    {
        int i = 0;
        stack s = new stack();
        s.top = -1;
        int element, next;
  
        /* push the first element to stack */
        s.push(arr[0]);
  
        // iterate for rest of the elements
        for (i = 1; i < n; i++) 
        {
            next = arr[i];
  
            if (s.isEmpty() == false)
            {
  
                // if stack is not empty, then
                // pop an element from stack
                element = s.pop();
  
                /* 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 (element < next) 
                {
                    System.out.println(element + " --> "
                                       + next);
                    if (s.isEmpty() == true)
                        break;
                    element = s.pop();
                }
  
                /* If element is greater than next, then
                   push the element back */
                if (element > next)
                    s.push(element);
            }
  
            /* push next to stack so that we can find next
               greater for it */
            s.push(next);
        }
  
        /* After iterating over the loop, the remaining
           elements in stack do not have the next greater
           element, so print -1 for them */
        while (s.isEmpty() == false)
        {
            element = s.pop();
            next = -1;
            System.out.println(element + " -- " + next);
        }
    }
  
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 11, 13, 21, 3 };
        int n = arr.length;
        printNGE(arr, n);
    }
}
  
// Thanks to Rishabh Mahrsee for contributing this code

Python

# Python program to print next greater element using stack
  
# Stack Functions to be used by printNGE()
  
  
def createStack():
    stack = []
    return stack
  
  
def isEmpty(stack):
    return len(stack) == 0
  
  
def push(stack, x):
    stack.append(x)
  
  
def pop(stack):
    if isEmpty(stack):
        print("Error : stack underflow")
    else:
        return stack.pop()
  
  
'''prints element and NGE pair for all elements of
   arr[] '''
  
  
def printNGE(arr):
    s = createStack()
    element = 0
    next = 0
  
    # push the first element to stack
    push(s, arr[0])
  
    # iterate for rest of the elements
    for i in range(1, len(arr), 1):
        next = arr[i]
  
        if isEmpty(s) == False:
  
            # if stack is not empty, then pop an element from stack
            element = pop(s)
  
            '''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 element < next:
                print(str(element) + " -- " + str(next))
                if isEmpty(s) == True:
                    break
                element = pop(s)
  
            '''If element is greater than next, then push
               the element back '''
            if element > next:
                push(s, element)
  
        '''push next to stack so that we can find
           next greater for it '''
        push(s, next)
  
    '''After iterating over the loop, the remaining
       elements in stack do not have the next greater
       element, so print -1 for them '''
  
    while isEmpty(s) == False:
        element = pop(s)
        next = -1
        print(str(element) + " -- " + str(next))
  
  
# Driver code
arr = [11, 13, 21, 3]
printNGE(arr)
  
# This code is contributed by Sunny Karira

C#

using System;
  
// c# program to print next
// greater element using stack
  
public class NGE {
    public class stack {
        public int top;
        public int[] items = new int[100];
  
        // Stack functions to be used by printNGE
        public virtual void push(int x)
        {
            if (top == 99) {
                Console.WriteLine("Stack full");
            }
            else {
                items[++top] = x;
            }
        }
  
        public virtual int pop()
        {
            if (top == -1) {
                Console.WriteLine("Underflow error");
                return -1;
            }
            else {
                int element = items[top];
                top--;
                return element;
            }
        }
  
        public virtual bool Empty
        {
            get { return (top == -1) ? true : false; }
        }
    }
  
    /* prints element and NGE pair for
       all elements of arr[] of size n */
    public static void printNGE(int[] arr, int n)
    {
        int i = 0;
        stack s = new stack();
        s.top = -1;
        int element, next;
  
        /* push the first element to stack */
        s.push(arr[0]);
  
        // iterate for rest of the elements
        for (i = 1; i < n; i++) {
            next = arr[i];
  
            if (s.Empty == false) {
  
                // if stack is not empty, then
                // pop an element from stack
                element = s.pop();
  
                /* 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 (element < next) {
                    Console.WriteLine(element + " --> "
                                      + next);
                    if (s.Empty == true) {
                        break;
                    }
                    element = s.pop();
                }
  
                /* If element is greater than next, then
                   push the element back */
                if (element > next) {
                    s.push(element);
                }
            }
  
            /* push next to stack so that we can find next
               greater for it */
            s.push(next);
        }
  
        /* 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) {
            element = s.pop();
            next = -1;
            Console.WriteLine(element + " -- " + next);
        }
    }
  
    // Driver Code
    public static void Main(string[] args)
    {
        int[] arr = new int[] { 11, 13, 21, 3 };
        int n = arr.Length;
        printNGE(arr, n);
    }
}
  
// This code is contributed by Shrikant13

Javascript

<script>
  
// A Stack based Javascript program to find next
// greater element for all array elements.
  
/* prints element and NGE pair for all
elements of arr[] of size n */
function printNGE(arr, n)
{
    var s = [];
  
    /* push the first element to stack */
    s.push(arr[0]);
  
    // iterate for rest of the elements
    for (var i = 1; i < n; i++) 
    {
  
        if (s.length == 0) {
            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.length ==0 == false 
               && s[s.length-1] < arr[i]) 
        {
            document.write( s[s.length-1] 
                 + " --> " + arr[i]+"<br>");
            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.length !=0) {
        document.write( s[s.length-1] + " --> " + -1+ "<br>" );
        s.pop();
    }
}
  
/* Driver code */
var arr = [11, 13, 21, 3];
var n = arr.length;
printNGE(arr, n);
  
</script>
Producción

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.  

  1. Inicialmente empujado a la pila.
  2. Se extrae de la pila cuando se procesa el siguiente elemento.
  3. Empujado de nuevo a la pila porque el siguiente elemento es más pequeño.
  4. 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;
}

Java

// A Stack based Java program to find next
// greater element for all array elements
// in same order as input.
import java.util.Stack;
  
class NextGreaterElement {
  
    static int arr[] = { 11, 13, 21, 3 };
  
    /* prints element and NGE pair for all
    elements of arr[] of size n */
    public static void printNGE()
    {
        Stack<Integer> s = new Stack<>();
        int nge[] = new int[arr.length];
  
        // iterate for rest of the elements
        for (int i = arr.length - 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.peek() <= arr[i])
                {
                    s.pop();
                }
            }
            nge[i] = s.empty() ? -1 : s.peek();
            s.push(arr[i]);
        }
        for (int i = 0; i < arr.length; i++)
            System.out.println(arr[i] + 
                               " --> " + nge[i]);
    }
  
    /* Driver Code */
    public static void main(String[] args)
    {
        // NextGreaterElement nge = new
        // NextGreaterElement();
        printNGE();
    }
}

Python3

# Python code to implement the approach
  
# prints element and NGE pair for all
# elements of arr[] of size n
def printNGE(arr, n):
  
    s = []
    res = [0 for i in range(n)]
  
    # iterate for rest of the elements
    for i in range(n-1,-1,-1):
  
        # /* 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 (len(s) != 0):
            while (len(s) != 0 and s[-1] <= arr[i]):
                s.pop()
        res[i] = -1 if len(s) == 0 else s[-1]
        s.append(arr[i])
  
    for i in range(len(arr)):
        print(str(arr[i]) + " --> " + str(res[i]))
      
# Driver Code
arr = [ 11, 13, 21, 3 ]
n = len(arr)
  
# Function call
printNGE(arr, n)
  
# This code is contributed by shinjanpatra

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 {
    private int[] arr = new int[] { 11, 13, 21, 3 };
  
    /* prints element and NGE pair for all
    elements of arr[] of size n */
    private void printNGE()
    {
        Stack<int> s = new Stack<int>();
        int[] nge = new int[arr.Length];
  
        // iterate for rest of the elements
        for (int i = arr.Length - 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.Count > 0) 
            {
                while (s.Count > 0 
                       && s.Peek() <= arr[i])
                {
                    s.Pop();
                }
            }
            nge[i] = s.Count == 0 ? -1 : s.Peek();
            s.Push(arr[i]);
        }
        for (int i = 0; i < arr.Length; i++) 
        {
            Console.WriteLine(arr[i] + " --> " + nge[i]);
        }
    }
  
    // Driver Code
    public static void Main(string[] args)
    {
        GFG nge = new GFG();
        nge.printNGE();
    }
}

Javascript

<script>
  
// Javascript program for the above approach
  
    /* prints element and NGE pair for all
    elements of arr[] of size n */
    function printNGE(arr, n)
    {
        var s = [];
        let res = new Array(n);
  
        // iterate for rest of the elements
        for (let 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.length != 0)
            {
                while (s.length != 0 
                       && s[s.length-1] <= arr[i])
                {
                    s.pop();
                }
            }
            res[i] = s.length == 0 ? -1 : s[s.length-1];
            s.push(arr[i]);
        }
        for (let i = 0; i < arr.length; i++)
            document.write(arr[i] + 
                               " --> " + res[i] + "<br/>");
    }
      
// Driver Code
  
       let arr = [ 11, 13, 21, 3 ];
    let n = arr.length;
  
    // Function call
    prletNGE(arr, n);
      
    // This code is contributed by splevel62.
</script>
Producción

11 ---> 13
13 ---> 21
21 ---> -1
3 ---> -1

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)
 

Método 3:

1. Este es el mismo que el método anterior, pero los elementos se empujan y se colocan solo una vez en la pila. La array se cambia de lugar. Los elementos de la array se insertan en la pila hasta que encuentra el elemento más grande a la derecha de la array. En otras palabras, los elementos se extraen de la pila cuando el valor superior de la pila es más pequeño en el elemento de array actual.

2. Una vez que todos los elementos se procesan en la array, pero la pila no está vacía. Los elementos dejados fuera de la pila no encuentran ningún elemento mayor. Así que saque el elemento de la pila y cambie su valor de índice como -1 en la array.

C++

// C++ code to implement the approach
  
#include <bits/stdc++.h>
  
using namespace std;
  
void nextLargerElement(int arr[], int n)
{
    vector<unordered_map<string, int> > s;
  
    // iterating over the array
    for (int i = 0; i < n; i++) {
        while (s.size() > 0
               && s[s.size() - 1]["value"] < arr[i]) {
            // updating the array as per the stack top
            unordered_map<string, int> d = s[s.size() - 1];
            s.pop_back();
            arr[d["ind"]] = arr[i];
        }
        // pushing values to stack
        unordered_map<string, int> e;
  
        e["value"] = arr[i];
        e["ind"] = i;
        s.push_back(e);
    }
  
    // updating the array as per the stack top
    while (s.size() > 0) {
        unordered_map<string, int> d = s[s.size() - 1];
        s.pop_back();
        arr[d["ind"]] = -1;
    }
}
  
// Driver Code
  
int main()
{
    int arr[] = { 6, 8, 0, 1, 3 };
    int n = 5;
  
    // Function call
    nextLargerElement(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
  
// This code is contributed by phasing17

Python3

# Python3 code
class Solution:
    def nextLargerElement(self,arr,n):
        #code here
        s=[]
        for i in range(len(arr)):
            while s and s[-1].get("value") < arr[i]:
                d = s.pop()
                arr[d.get("ind")] = arr[i]
            s.append({"value": arr[i], "ind": i})
        while s:
            d = s.pop()
            arr[d.get("ind")] = -1
        return arr
          
if __name__ == "__main__":
    print(Solution().nextLargerElement([6,8,0,1,3],5))

Javascript

// JS code to implement the approach
function nextLargerElement(arr, n)
{
    var s = [];
      
    // iterating over the array
    for (var i = 0; i < arr.length; i++)
    {
        while (s.length > 0 && s[s.length - 1]["value"] < arr[i])
        {
            // updating the array as per the stack top
            var d = s.pop();
            arr[d["ind"]] = arr[i];
        }
        // pushing values to stack
        s.push({"value": arr[i], "ind": i});
    }
      
    // updating the array as per the stack top
    while (s.length > 0)
    {
        d = s.pop();
        arr[d["ind"]] = -1;
    }
    return arr;
      
}
  
// Driver Code
var arr = [6, 8, 0, 1, 3];
var n = 5;
  
// Function call
console.log(nextLargerElement(arr, n));
  
// This code is contributed by phasing17
Producción

[8, -1, 1, 3, -1]

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)

Consulte para obtener una solución optimizada para imprimir en el mismo orden.
 

 

Escriba comentarios si encuentra que los códigos/algoritmos anteriores son incorrectos o encuentra otras formas de resolver el mismo problema.
 

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 *