Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nFirst, find the nge using decreasing stack.\n\nThen for each nge, store every element t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFirst, find the nge using decreasing stack.\n\nThen for each nge, store every element that touches it or pops it off during this process, as these are the second next greater element candidates. If any element that doesn\'t directly touch it during the nge process, then there is an element larger than it that appears before it which must be touching the nge on the stack. So this element can never be the second nge anyway.\n\nSo each element will "touch" only one other element on the stack so the total length of the lists will not exceed n.\n\nSort each list for each element.\n\nFor every element, if nge element exists, go to its list and find the smallest element > nums[i] with binary search, this will be the second next greater element.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> secondGreaterElement(vector<int>& nums) {\n        // nums[i] < nums[j]\n        // nums[i] < nums[k] and i < j < k\n        //\n\n        int n = nums.size();\n\n        vector<int> nge(n, -1);\n\n        vector<vector<int>> list(n);\n\n        stack<int> s;\n\n        for(int i = 0; i<n; i++)\n        {\n            while(!s.empty() && nums[i] > nums[s.top()])\n            {\n                list[s.top()].push_back(nums[i]);\n                nge[s.top()] = i;\n                s.pop();\n            }\n\n            if(!s.empty())\n            {\n                list[s.top()].push_back(nums[i]);\n            }\n            s.push(i);\n        }\n\n        for(int i = 0; i<n; i++)\n        {\n            sort(list[i].begin(), list[i].end());\n        }\n\n        vector<int> nge2(n, -1);\n\n        for(int i = 0; i<n; i++)\n        {\n            if(nge[i] != -1)\n            {\n                int len = list[nge[i]].size();\n                if(len == 0)\n                {\n                    continue;\n                }\n\n                int lo = 0;\n                int hi = len-1;\n                int ans = -1;\n\n                while(lo <= hi)\n                {\n                    int mid = lo + (hi - lo)/2;\n                    if(list[nge[i]][mid] > nums[i])\n                    {   \n                        ans = mid;\n                        hi = mid-1;\n                    }\n                    else\n                    {\n                        lo = mid+1;\n                    }\n                }\n\n                if(ans != -1)\n                {\n                    nge2[i] = list[nge[i]][ans];\n                }\n            }\n        }\n\n\n        return nge2;\n    }\n};\n```
['C++']