C++ Two Monotonic Stacks and a Transfer Stack
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires finding the second greater element for each element in the array. 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires finding the second greater element for each element in the array. My first thought was to use a stack to keep track of elements for which we need to find the next greater element and another stack to track elements for which we need to find the second greater element. By maintaining these stacks, we can efficiently determine the second greater element.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Initialize three stacks: `waitforgreater` for elements waiting to find their next greater element, `waitforsecondgreater` for elements waiting to find their second greater element, and `temp` as a temporary stack to assist in transferring elements.\n2. Initialize a result vector with -1s to store the second greater elements.\n3. Iterate through the array:\n   - For each element, check if it is greater than the top of the `waitforgreater` stack. If it is, pop from the `waitforgreater` stack and update the result for the corresponding index.\n   - Move elements from the `waitforsecondgreater` stack to the `temp` stack if the current element is greater than the top of the `waitforsecondgreater` stack.\n   - Transfer elements from the `temp` stack to the `waitforgreater` stack.\n   - Push the current element onto the `waitforsecondgreater` stack.\n4. Return the result vector.\n\n### Detailed Logic:\n- We use `waitforsecondgreater` to keep track of elements that are waiting to find their second greater element.\n- As we iterate through the array, if the current element is greater than the top element of `waitforsecondgreater`, it means we have found the next greater element for that element. We then move this element to the `waitforgreater` stack since it now waits to find its second greater element.\n- By using the `temp` stack, we ensure the order of elements is maintained when transferring between `waitforsecondgreater` and `waitforgreater`. This way, the smallest element is always on top, maintaining an increasing order in both stacks.\n- After processing the current element, we push it onto the `waitforsecondgreater` stack, where it will wait to find its second greater element.\n- The final result is obtained by updating the elements in the result vector as we find the second greater elements for each index.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$, where n is the number of elements in the array. Each element is pushed and popped from the stacks at most twice.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$, as we use three stacks and a result vector of size n.\n\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> secondGreaterElement(vector<int>& nums) {\n        stack<pair<int,int>> waitforgreater;\n        stack<pair<int,int>> waitforsecondgreater;\n        stack<pair<int,int>> temp;\n        vector<int> result(nums.size(), -1);\n        \n        waitforsecondgreater.push(make_pair(0, nums[0]));\n        \n        for(int i = 1; i < nums.size(); i++) {\n            while(!waitforgreater.empty() && waitforgreater.top().second < nums[i]) {\n                result[waitforgreater.top().first] = nums[i];\n                waitforgreater.pop();\n            }\n            \n            while(!waitforsecondgreater.empty() && waitforsecondgreater.top().second < nums[i]) {\n                temp.push(waitforsecondgreater.top());\n                waitforsecondgreater.pop();\n            }\n            \n            while(!temp.empty()) {\n                waitforgreater.push(temp.top());\n                temp.pop();\n            }\n            \n            waitforsecondgreater.push(make_pair(i, nums[i]));\n        }\n        \n        return result;\n    }\n};\n\n```
['C++']