C++ | Set + Monotonic Stack | Easy To Understand
In order to solve this problem, we need to have basic idea on how to calculate the next greater element using monotonic stack. \n2. Monotonic stack is basically
1. In order to solve this problem, we need to have basic idea on how to calculate the next greater element using monotonic stack. \n2. Monotonic stack is basically a stack in decreasing order such that all elements are in descending order. Whenever we encounter a new number such that it\'s value is greater than the element on the top, we keep on popping all the numbers from the stack out till the stack\'s topmost value is greater than the current value. Using this, we can easily find the next greater element.\n3. Idea behind this problem is that whenever we encounter a next greater element, we will add all the elements whose next greater element is the current element to a different set called `processed`. This is for keeping track that first greater element of these numbers have been found already.\n4. Whenever I encounter next number, I will first go through the processed set. If I encounter a number which is less than current element, the current element will be the second greater number for the processed one. We can then update our answer and delete this value from our set.\n```\nclass Solution {\npublic:\n    vector<int> secondGreaterElement(vector<int>& nums) {\n        stack<pair<int, int> > monoStack;\n        set<pair<int, int> > processed;\n        vector<int> ans(nums.size(), -1);\n        for(int i = 0; i < nums.size(); i++) {\n            vector<pair<int, int> > toDelete;\n            for(auto it = processed.begin(); it != processed.end(); it++) {\n                if(it->first < nums[i]) {\n                    ans[it->second] = nums[i];\n                    toDelete.push_back(*it);\n                }\n                else break;\n            }\n            for(int j = 0; j < toDelete.size(); j++) {\n                processed.erase(toDelete[j]);\n            }\n            if(monoStack.empty()) monoStack.push({ nums[i], i });\n            else {\n                while(!monoStack.empty() && monoStack.top().first < nums[i]) {\n                    processed.insert(monoStack.top());\n                    monoStack.pop();\n                }\n                monoStack.push({ nums[i], i });\n            }\n        }\n        return ans;\n    }\n};\n```
['C', 'Monotonic Stack', 'Ordered Set']