C++ || Two Solution || Same as Next Greater Element  || Segment Tree
\n# Solution 1\nclass Solution {\npublic:\n    vector<int> secondGreaterElement(vector<int>& nums) {\n        int n = nums.size();\n        \n        // next gr
```\n# Solution 1\nclass Solution {\npublic:\n    vector<int> secondGreaterElement(vector<int>& nums) {\n        int n = nums.size();\n        \n        // next greater\n        vector<int> ng(n, -1);\n        stack<int> stk;\n        for(int i = n-1; i >= 0; i--) {\n            while(!stk.empty() && nums[stk.top()] <= nums[i])\n                stk.pop();\n            if(!stk.empty())\n                ng[i] = stk.top();\n            stk.push(i);\n        }\n        \n        // next second greater\n        vector<int> sg(n, -1);\n        for(int i = 0; i < n; i++) {\n            if(ng[i] == -1)\n                continue;\n            int tmp = ng[i]+1;\n            while(tmp != -1 && tmp < n && nums[tmp] <= nums[i])\n                tmp = ng[tmp];\n            if(tmp != -1 && tmp < n)\n                sg[i] = nums[tmp];\n        }\n        \n        return sg;\n    }\n};\n\n#Solution 2\nclass Solution {\n    vector<int> tree;\n\n    // range max tree\n    int buildTree(int i, int l, int r, vector<int> &nums) {\n        if (l == r) \n            return tree[i] = nums[l];\n        int mid = (l + r) / 2;\n        return tree[i] = max(buildTree(2*i+1, l, mid, nums), buildTree(2*i+2, mid+1, r, nums));\n    }\n\n    int query(int num, int pos, int i, int l, int r, vector<int> &nums) {\n        if(tree[i] <= num || r < pos)\n            return INT_MAX;\n        else if(l == r)\n            return l;\n\n        int mid = (l + r) / 2;\n        int res = query(num, pos, 2*i+1, l, mid, nums);\n        if (res == INT_MAX)\n            res = query(num, pos, 2*i+2, mid+1, r, nums);\n\n        return res;\n    }\n\npublic:\n    vector<int> secondGreaterElement(vector<int>& nums) {\n        int n = nums.size();\n        vector<int> ans(n, -1);\n\n        tree.resize(4*n);\n        buildTree(0, 0, n-1, nums);\n\n        for (int i = 0; i < n; i++) {\n            int ng = query(nums[i], i+1, 0, 0, n-1, nums);\n            if(ng != INT_MAX) {\n                int sng = query(nums[i], ng+1, 0, 0, n-1, nums);\n                cout << sng << " ";\n                if(sng != INT_MAX)\n                    ans[i] = nums[sng];\n            } \n        }\n\n        return ans;\n    }\n};\n\n\n```
['Stack', 'Segment Tree', 'C', 'Monotonic Stack']