C++ Easy Solution using Stack and Binary Search | O(NLogN) Time & O(N) Space Complexity
Intuition\nWe can get inspiration to use Stack from Next Greater Element II. Then we have to find a way to now instead obtain the second greater element instead
# Intuition\nWe can get inspiration to use Stack from [Next Greater Element II](https://leetcode.com/problems/next-greater-element-ii/). Then we have to find a way to now instead obtain the second greater element instead of first.\n\n# Approach\nRead the solution for [Next Greater Element II](https://leetcode.com/problems/next-greater-element-ii/) before reading this if you haven\'t as the approach is heavily based on that. While popping elements before pushing the new element, we will also store them in an vector. As the elements were always sorted in the stack, the vector will be sorted to, thus we use can binary search. Now to find the second greater element, we first find the first greater element. Then to find the second greater element:\n\n- If there is any number greater than the required number in the vector of numbers removed while pushing the first greater element, then the lowest such number is the answer\n- Otherwise just pick the next number from stack\n\nAlso remember to handle the edge case when answer is -1.\n\n# Complexity\n- Time complexity: O(nlogn)\n\n- Space complexity: O(n)\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> secondGreaterElement(vector<int>& nums) {\n        int n = nums.size();\n        vector<int> ans(n);\n        vector<vector<int>> del(n, vector<int> ());\n        stack<pair<int, int>> data;\n        for(int i = n - 1; i >= 0; i--){\n            if(data.empty()){\n                ans[i] = -1;\n                data.push({nums[i], i});\n                continue;\n            }\n            while(data.top().first <= nums[i]){\n                del[i].push_back(data.top().first);\n                data.pop();\n                if(data.empty()){\n                    break;\n                }\n            }\n            if(data.empty()){\n                ans[i] = -1;\n                data.push({nums[i], i});\n                continue;\n            }\n            auto itr = upper_bound(del[data.top().second].begin(), del[data.top().second].end(), nums[i]);\n            if(itr == del[data.top().second].end()){\n                pair<int, int> temp = data.top();\n                data.pop();\n                if(data.empty()) ans[i] = -1;\n                else ans[i] = data.top().first;\n                data.push(temp);\n            }else ans[i] = *itr;\n            data.push({nums[i], i});\n        }\n        return ans;\n    }\n};\n```
['Binary Search', 'Stack', 'C++']