C++ stack + unordered_map

• ``````class Solution {
public:
vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
stack<int> s;
unordered_map<int, int> m;
for (int n : nums) {
while (s.size() && s.top() < n) {
m[s.top()] = n;
s.pop();
}
s.push(n);
}
vector<int> ans;
for (int n : findNums) ans.push_back(m.count(n) ? m[n] : -1);
return ans;
}
};
``````

• @lzl124631x perfect solution

• @lzl124631x Nice idea,thank you very much!

• ingenious!!!!!

• @lzl124631x

WHAT A NICE SOLUTION!

My answer, by the comparison, is too simple!

• awsome, but not easy to understand

• @lzl124631x perfect!

• thank you for your good idea!

• Thank you! Very Good Idea!!!

• nice solution!
Good to see someone solving this problem from the view of stack.

• Bravo! Thanks for sharing this neat O(n) method.@lzl124631x
I didn't realize my own solution was O(n2) until I read yours.

• brilliant, same with mine

• learn from your solution. Thx.

• This post is deleted!

• Very cool solution. The only problem is it's not "pay for play". I.e., it pre-computes the Next Greatest Element for all elements of nums. So, if the size of findNums is much smaller than that of nums (e.g. 1 vs 1000) all that effort is wasted. However, if they are of close to similar size, then this is optimal.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.