Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.
Examples: a) For any array, rightmost element always has next greater element as -1. b) For an array which is sorted in decreasing order, all elements have next greater element as -1. c) For the input array [4, 5, 2, 25}, the next greater elements for each element are as follows.
Element NGE 4 --> 5 5 --> 25 2 --> 25 25 --> -1
Method (Using Stack)
//https://www.geeksforgeeks.org/next-greater-element/
#include <iostream>
using namespace std;
void func (int a[], int n) {
int nge[n], s[n], top=-1;
s[++top]= 0;
for (int i=0; i<n; i++) {
if (top== -1) {
s[++top]= i;
continue;
}
while (top!= -1 && a[s[top]]< a[i]) {
nge[s[top--]]= a[i];
}
s[++top]= i;
}
while (top!= -1)
nge[s[top--]]= -1;
for (int i=0; i<n; i++)
cout<< a[i] << "-->"<< nge[i] << "\n";
}
int main () {
int n;
cin>>n;
int a[n];
for (int i=0; i<n; i++)
cin>> a[i];
func (a,n);
}