Dada una array de n elementos y q consultas, para cada consulta que tenga índice i, encuentre el siguiente elemento mayor e imprima su valor. Si no hay un elemento mayor a su derecha, imprima -1.
Ejemplos:
Input : arr[] = {3, 4, 2, 7, 5, 8, 10, 6}
query indexes = {3, 6, 1}
Output: 8 -1 7
Explanation :
For the 1st query index is 3, element is 7 and
the next greater element at its right is 8
For the 2nd query index is 6, element is 10 and
there is no element greater than 10 at right,
so print -1.
For the 3rd query index is 1, element is 4 and
the next greater element at its right is 7.
Enfoque normal: un enfoque normal será que cada consulta se mueva en un bucle desde el índice hasta n y encuentre el siguiente elemento mayor e imprímalo, pero esto en el peor de los casos tomará n iteraciones, que es mucho si la cantidad de consultas son altos.
Complejidad de tiempo: O(n^2)
Espacio auxiliar>: O(1)
Enfoque eficiente:
Un enfoque eficiente se basa en el siguiente elemento mayor . Almacenamos el índice del siguiente elemento mayor en una array y para cada proceso de consulta, respondemos la consulta en O(1) que la hará más eficiente.
Pero para encontrar el siguiente elemento mayor para cada índice en la array, hay dos formas.
Uno tomará o(n^2) y O(n)space que será iterar desde I+1 hasta n para cada elemento en el índice I y encontrar el siguiente elemento mayor y almacenarlo.
Pero el más eficiente será usar stack, donde usamos índices para comparar y almacenar en next[] el siguiente índice de elemento mayor.
1) Empuje el primer índice para apilar.
2) Elija el resto de los índices uno por uno y siga los siguientes pasos en bucle.
….a) Marque el elemento actual como i.
….b) Si la pila no está vacía, extraiga un índice de la pila y compare un [índice] con una [I].
….c) Si a[I] es mayor que a[índice], entonces a[I] es el siguiente elemento mayor para a[índice].
….d) Siga sacando de la pila mientras el elemento de índice sacado es más pequeño que a[I]. a[I] se convierte en el siguiente elemento mayor para todos esos elementos reventados
….g) Si a[I] es más pequeño que el elemento de índice reventado, entonces empuje el índice reventado hacia atrás.
3) Después de que termine el bucle en el paso 2, extraiga todos los índices de la pila e imprima -1 como el siguiente índice para ellos.
C++
// C++ program to print
// next greater number
// of Q queries
#include <bits/stdc++.h>
using namespace std;
// array to store the next
// greater element index
void next_greatest(int next[],
int a[], int n)
{
// use of stl
// stack in c++
stack<int> s;
// push the 0th
// index to the stack
s.push(0);
// traverse in the
// loop from 1-nth index
for (int i = 1; i < n; i++)
{
// iterate till loop is empty
while (!s.empty()) {
// get the topmost
// index in the stack
int cur = s.top();
// if the current element is
// greater than the top indexth
// element, then this will be
// the next greatest index
// of the top indexth element
if (a[cur] < a[i])
{
// initialise the cur
// index position's
// next greatest as index
next[cur] = i;
// pop the cur index
// as its greater
// element has been found
s.pop();
}
// if not greater
// then break
else
break;
}
// push the i index so that its
// next greatest can be found
s.push(i);
}
// iterate for all other
// index left inside stack
while (!s.empty())
{
int cur = s.top();
// mark it as -1 as no
// element in greater
// then it in right
next[cur] = -1;
s.pop();
}
}
// answers all
// queries in O(1)
int answer_query(int a[], int next[],
int n, int index)
{
// stores the next greater
// element positions
int position = next[index];
// if position is -1 then no
// greater element is at right.
if (position == -1)
return -1;
// if there is a index that
// has greater element
// at right then return its
// value as a[position]
else
return a[position];
}
// Driver Code
int main()
{
int a[] = {3, 4, 2, 7,
5, 8, 10, 6 };
int n = sizeof(a) / sizeof(a[0]);
// initializes the
// next array as 0
int next[n] = { 0 };
// calls the function
// to pre-calculate
// the next greatest
// element indexes
next_greatest(next, a, n);
// query 1 answered
cout << answer_query(a, next, n, 3) << " ";
// query 2 answered
cout << answer_query(a, next, n, 6) << " ";
// query 3 answered
cout << answer_query(a, next, n, 1) << " ";
}
Java
// Java program to print
// next greater number
// of Q queries
import java.util.*;
class GFG
{
public static int[] query(int arr[],
int query[])
{
int ans[] = new int[arr.length];// this array contains
// the next greatest
// elements of all the elements
Stack<Integer> s = new Stack<>();
// push the 0th index
// to the stack
s.push(arr[0]);
int j = 0;
//traverse rest
// of the array
for(int i = 1; i < arr.length; i++)
{
int next = arr[i];
if(!s.isEmpty())
{
// get the topmost
// element in the stack
int element = s.pop();
/* If the popped element
is smaller than next,
then a) store the pair
b) keep popping while
elements are smaller and
stack is not empty */
while(next > element)
{
ans[j] = next;
j++;
if(s.isEmpty())
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 -1 for them */
while(!s.isEmpty())
{
int element = s.pop();
ans[j] = -1;
j++;
}
// return the next
// greatest array
return ans;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {3, 4, 2, 7,
5, 8, 10, 6};
int query[] = {3, 6, 1};
int ans[] = query(arr,query);
// getting output array
// with next greatest elements
for(int i = 0; i < query.length; i++)
{
// displaying the next greater
// element for given set of queries
System.out.print(ans[query[i]] + " ");
}
}
}
// This code was contributed
// by Harshit Sood
Python3
# Python3 program to print # next greater number # of Q queries # array to store the next # greater element index def next_greatest(next, a, n): # use of stl # stack in c++ s = [] # push the 0th # index to the stack s.append(0); # traverse in the # loop from 1-nth index for i in range(1, n): # iterate till loop is empty while (len(s) != 0): # get the topmost # index in the stack cur = s[-1] # if the current element is # greater then the top indexth # element, then this will be # the next greatest index # of the top indexth element if (a[cur] < a[i]): # initialise the cur # index position's # next greatest as index next[cur] = i; # pop the cur index # as its greater # element has been found s.pop(); # if not greater # then break else: break; # push the i index so that its # next greatest can be found s.append(i); # iterate for all other # index left inside stack while(len(s) != 0): cur = s[-1] # mark it as -1 as no # element in greater # then it in right next[cur] = -1; s.pop(); # answers all # queries in O(1) def answer_query(a, next, n, index): # stores the next greater # element positions position = next[index]; # if position is -1 then no # greater element is at right. if(position == -1): return -1; # if there is a index that # has greater element # at right then return its # value as a[position] else: return a[position]; # Driver Code if __name__=='__main__': a = [3, 4, 2, 7, 5, 8, 10, 6 ] n = len(a) # initializes the # next array as 0 next=[0 for i in range(n)] # calls the function # to pre-calculate # the next greatest # element indexes next_greatest(next, a, n); # query 1 answered print(answer_query(a, next, n, 3), end = ' ') # query 2 answered print(answer_query(a, next, n, 6), end = ' ') # query 3 answered print(answer_query(a, next, n, 1), end = ' ') # This code is contributed by rutvik_56.
C#
// C# program to print next greater
// number of Q queries
using System;
using System.Collections.Generic;
class GFG
{
public static int[] query(int[] arr,
int[] query)
{
int[] ans = new int[arr.Length]; // this array contains
// the next greatest
// elements of all the elements
Stack<int> s = new Stack<int>();
// push the 0th index to the stack
s.Push(arr[0]);
int j = 0;
// traverse rest of the array
for (int i = 1; i < arr.Length; i++)
{
int next = arr[i];
if (s.Count > 0)
{
// get the topmost element in the stack
int element = s.Pop();
/* If the popped element is smaller
than next, then
a) store the pair
b) keep popping while
elements are smaller and
stack is not empty */
while (next > element)
{
ans[j] = next;
j++;
if (s.Count == 0)
{
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 -1 for them */
while (s.Count > 0)
{
int element = s.Pop();
ans[j] = -1;
j++;
}
// return the next greatest array
return ans;
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = new int[] {3, 4, 2, 7, 5, 8, 10, 6};
int[] query = new int[] {3, 6, 1};
int[] ans = GFG.query(arr, query);
// getting output array
// with next greatest elements
for (int i = 0; i < query.Length; i++)
{
// displaying the next greater
// element for given set of queries
Console.Write(ans[query[i]] + " ");
}
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// JavaScript program to print
// next greater number
// of Q queries
// array to store the next
// greater element index
function next_greatest(next, a, n)
{
// use of stl
// stack in c++
var s = [];
// push the 0th
// index to the stack
s.push(0);
// traverse in the
// loop from 1-nth index
for (var i = 1; i < n; i++)
{
// iterate till loop is empty
while (s.length!=0) {
// get the topmost
// index in the stack
var cur = s[s.length-1];
// if the current element is
// greater then the top indexth
// element, then this will be
// the next greatest index
// of the top indexth element
if (a[cur] < a[i])
{
// initialise the cur
// index position's
// next greatest as index
next[cur] = i;
// pop the cur index
// as its greater
// element has been found
s.pop();
}
// if not greater
// then break
else
break;
}
// push the i index so that its
// next greatest can be found
s.push(i);
}
// iterate for all other
// index left inside stack
while (s.length!=0)
{
var cur = s[s.length-1];
// mark it as -1 as no
// element in greater
// then it in right
next[cur] = -1;
s.pop();
}
}
// answers all
// queries in O(1)
function answer_query(a, next, n, index)
{
// stores the next greater
// element positions
var position = next[index];
// if position is -1 then no
// greater element is at right.
if (position == -1)
return -1;
// if there is a index that
// has greater element
// at right then return its
// value as a[position]
else
return a[position];
}
// Driver Code
var a = [3, 4, 2, 7,
5, 8, 10, 6];
var n = a.length;
// initializes the
// next array as 0
var next = Array(n).fill(0);
// calls the function
// to pre-calculate
// the next greatest
// element indexes
next_greatest(next, a, n);
// query 1 answered
document.write( answer_query(a, next, n, 3) + " ");
// query 2 answered
document.write( answer_query(a, next, n, 6) + " ");
// query 3 answered
document.write( answer_query(a, next, n, 1) + " ");
</script>
Producción:
8 -1 7
Complejidad de tiempo: max(O(n), O(q)), O(n) para preprocesar la siguiente array [] y O(1) para cada consulta.
Espacio auxiliar: O(n)
Este artículo es una contribución de Raja Vikramaditya(raj) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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