Next Greater Element

• Time : O(n)
• Space : O(n)

#include <vector>
using namespace std;

vector<int> nextGreaterElement(vector<int> array) {
  int n = array.size();
	vector<int> st;
	vector<int> res(n, INT_MIN);
	
	for(int i = n - 1; i >= 0; i--) {
		while(!st.empty() and st.back() <= array[i])
			st.pop_back();
		if(!st.empty())
			res[i] = st.back();
		st.push_back(array[i]);
	}
	
	for(int i = n - 1; i >= 0; i--) {
		if(res[i] != INT_MIN) continue;
		while(!st.empty() and st.back() <= array[i])
			st.pop_back();
		if(!st.empty())
			res[i] = st.back();
		else res[i] = -1;
	}
	
	
	
  return res;
}