C++ easy O(NlogN) monotonic stack || multiset || similar to next greater element
Approach\nwe have to find every element\'s next to next greater element, we can use a stack for finding an element\'s next greater element.\n\nso in the example
# Approach\nwe have to find every element\'s next to next greater element, we can use a stack for finding an element\'s next greater element.\n\nso in the example [2,4,0,9,6] next greater element for 2 is 4.\n\nas soon as next greater element of a number arrives, we can push that number in a multiset, and just lookout for one more greater element than that number which will be our answer.\n\nso in the example, as soon as 4 arrives (next greater of 2) we push 2 in a multiset, when 9 arrives, we check multiset whether the elements in the multiset are smaller than 9, all the elements smaller than 9 will have answer = 9.\n\n# Complexity\n- Time complexity:\nO(Nlog(N))\n\n- Space complexity:\nO(N)\n\n# Code\n```\nclass Solution {\npublic:\n\n    vector<int> secondGreaterElement(vector<int>& nums) {\n        stack<int> s;\n        multiset<vector<int>> m;\n        vector<int> ans(nums.size(),-1);\n        s.push(0);\n        for(int i=1;i<nums.size();i++){\n\n            // check if current element is greater than any element present in multiset\n            while(!m.empty() && nums[i] > (*m.begin())[0]){\n                ans[(*m.begin())[1]] = nums[i];\n                m.erase(m.begin());\n            }\n\n            // all the elements whose next greater element exist will be pushed in multiset, we keep this track with the help of stack\n            while(!s.empty() && nums[i]>nums[s.top()]){\n                m.insert({nums[s.top()],s.top()});\n                s.pop();\n            }\n            s.push(i);\n        }\n        return ans;\n    }\n};\n```
['C++']