Generalize to Kth Greater Element O(n * k)
Intuition\n Describe your first thoughts on how to solve this problem. \nSimilar to Next Greater Element I, we use monotonic stack to find the next greater elem
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSimilar to [Next Greater Element I](https://leetcode.com/problems/next-greater-element-i/), we use monotonic stack to find the next greater element. To find the second next greater element, we can save the elements that already has next greater element, and use this information to find the second greater elemet. We can either use priority queue or stack to save this information.\n\n# Priority Queue (min heap) Approach\n<!-- Describe your approach to solving the problem. -->\n\nIf using priority queue, we iterate the `nums` array and we find an element that has a next greater element, we push that element to the priority queue (min heap). if current element in `nums` is greater than smallest element from the priority queue, then that means current element is the second next greater element for element from the priority queue.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(nlogn)$$ - Each element is pushed to/popped from priority queue at most once\n\n- Space complexity:\n\n$$O(nlogn)$$ - Each element is pushed to/popped from priority queue at most once\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# C++ Code\n```\nclass Solution {\npublic:\n    vector<int> secondGreaterElement(vector<int>& nums) {\n        int n = nums.size();\n        vector<int> ans(n, -1);\n        stack<int> st;\n        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;\n        for (int i = 0; i < n; i++) {\n            while (!pq.empty() && pq.top()[0] < nums[i]) {\n                ans[pq.top()[1]] = nums[i];\n                pq.pop();\n            }\n            while (!st.empty() && nums[st.top()] < nums[i]) {\n                pq.push({nums[st.top()], st.top()});\n                st.pop();\n            }\n            st.push(i);\n        }\n        return ans;\n    }\n};\n```\n\n# Stack Approach\n<!-- Describe your approach to solving the problem. -->\n\nIf using stack, we iterate the `nums` array and we find an element that has a next greater element using first stack `st1`. Once we find this element, we push this element to the second stack `st2`. if current element in `nums` is greater than the top element from the `st2`, then that means current element is the second next greater element for element from the `st2`.\n\nOne thing to note is that since `st1` is decreasing monotonic stack, in order to preserve this order in `st2` as well, we need an additional stack `temp` to preserve the order. Otherwise we will miss some elements.\n\nEx) consider example `[3,0,4,3,2,1]`. We iterate the array:\n`i == 0`: 3 is pushed to `st1`. `st1` : `[3]`\n`i == 1`: 0 is pushed to `st1`. `st1` : `[3,0]`\n`i == 2`: Since 3 < 4 and 0 < 4, we push 3, 0 to `st2`. 4 is pushed to `st1`. `st1` : `[4]`, `st2` : `[3,0]`.\n`i == 3`: Since 0 < 3, we update `ans[1] = 3`, 0 is popped from `st2`. 3 is pushed to `st1`. `st1` : `[4,3]`, `st2` : `[3]`.\n`i == 4`: 2 is pushed to `st1`. `st1` : `[4,3,2]`, `st2` : `[3]`.\n`i == 5`: 1 is pushed to `st1`. `st1` : `[4,3,2,1]`, `st2` : `[3]`.\nThus, `ans` becomes `[-1,3,-1,-1,-1,-1]`\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$ - Each element is pushed to/popped from 2 stacks at most once\n\n- Space complexity:\n\n$$O(n)$$ - Each element is pushed to/popped from 2 stacks at most once\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# C++ Code\n```\nclass Solution {\npublic:\n    vector<int> secondGreaterElement(vector<int>& nums) {\n        int n = nums.size();\n        vector<int> ans(n, -1);\n        stack<int> st1, st2, temp;\n        for (int i = 0; i < nums.size(); i++) {\n            while (!st2.empty() && nums[st2.top()] < nums[i]) {\n                ans[st2.top()] = nums[i];\n                st2.pop();\n            }\n            while (!st1.empty() && nums[st1.top()] < nums[i]) {\n                temp.push(st1.top());\n                st1.pop();\n            }\n            while (!temp.empty()) {\n                st2.push(temp.top());\n                temp.pop();\n            }\n            st1.push(i);\n        }\n        return ans;\n    }\n};\n```\n\n# Generalize to Kth Greater Element\n<!-- Describe your approach to solving the problem. -->\n\nIf using stack, we iterate the `nums` array and we find an element that has a next greater element using first stack `st1`. Once we find this element, we push this element to the second stack `st2`. if current element in `nums` is greater than the top element from the `st2`, then that means current element is the second next greater element for element from the `st2`.\n\nUsing similar technique from previous solution, we can generalize our solution to Kth Greater Element by using `k` stacks. `stacks[i]` denotes the stack where its elements have `i`th greater element.\n\nNow, we iterate the `nums` array and we find an element that has a next greater element using first stack `stacks[0]`. We push this element to the second stack `stacks[1]`. If current element in `nums` is greater than the top element from the `stacks[1]`, then that means `stacks[1].top()` element has second next greater element. Thus we push `stacks[1].top()` element to next stack `stacks[2]`, and so on until we reach the last stack.\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(nk)$$ - Each element is pushed to/popped from each stack at most once\n\n- Space complexity:\n\n$$O(nk)$$ - Each element is pushed to/popped from each stack at most once\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# C++ Code\n```\nclass Solution {\npublic:\n    vector<int> secondGreaterElement(vector<int>& nums, int k = 2) {\n        int n = nums.size();\n        vector<int> ans(n, -1);\n        stack<int> temp;\n        vector<stack<int>> stacks(k);\n        for (int i = 0; i < nums.size(); i++) {\n            for (int j = k - 1; j >= 1; j--) {\n                while (!stacks[j].empty() && nums[stacks[j].top()] < nums[i]) {\n                    ans[stacks[j].top()] = nums[i];\n                    stacks[j].pop();\n                }\n                while (!stacks[j - 1].empty() && nums[stacks[j - 1].top()] < nums[i]) {\n                    temp.push(stacks[j - 1].top());\n                    stacks[j - 1].pop();\n                }\n                while (!temp.empty()) {\n                    stacks[j].push(temp.top());\n                    temp.pop();\n                }\n                if (j == 1) { \n                    stacks[j - 1].push(i); // first stack\n                }\n            }\n        }\n        return ans;\n    }\n};\n```
['Stack', 'Monotonic Stack', 'C++']