previous greater element
//program in C++ to find previous greater element
//following approach is better than naive approach because it does very less no.
//of comparisons between elements and skips unnecessary comparisons
#include <iostream>
#include <stack>
using namespace std;
void find_pge(int a[],int pge[],int n){
stack<int> s;
for(int i=n-1;i>=0;i--){
//if current element is greater than top of stack
while(!s.empty() && a[s.top()] < a[i]){
pge[s.top()] = a[i];
s.pop();
}
s.push(i);
}
//mark all remaining element's previous greater element to be -1(not present)
while(!s.empty()){
pge[s.top()] = -1;
s.pop();
}
}
int main() {
int a[5] = {5,4,3,4,5},pge[5];
find_pge(a,pge,5);
for(int i=0;i<5;i++){
cout<<"previous greater element for "<<a[i]<<" is "<<pge[i]<<"\n";
}
return 0;
}