Monotonic Stack + Min Heap
Intuition\nTo find the second greatest element. we need to distingush elements whose who have got one greater and whose who havent got any greater.\n Describe y
# Intuition\nTo find the second greatest element. we need to distingush elements whose who have got one greater and whose who havent got any greater.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nTo find the fist greater element we use monotonic stack `st` as in First Greatest Element. but after poping it we add it to a min heap `pq` which contains elements that have got a greater element once.\n\nBefore adding elements and even before poping elements to the `pq` we check for all elements that are less that the element and hece we get the second greatest element.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: *`O(nlogn)`*\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: *`O(n)`*\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        int n = nums.size();\n        vector<int> gE(n, -1);\n        stack<int> st;\n        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;\n        \n        for(int i = 0; i < n; i++) {\n            while(!pq.empty() && pq.top().first < nums[i]) {\n                gE[pq.top().second] = nums[i];\n                pq.pop();\n            }\n            while(!st.empty() && nums[st.top()] < nums[i]) {\n                pq.push(make_pair(nums[st.top()], st.top()));\n                st.pop();\n            }\n            st.push(i);\n        }\n        \n        return gE;\n    }\n};\n```
['Array', 'Heap (Priority Queue)', 'Monotonic Stack', 'C++']