My C++ implementation with idea from others.


  • 0
    W
        vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
            // Value -> Index mapping.
            map<int, int> Idx;
            unsigned N = findNums.size();
            for (int i = 0; i < N; ++i) {
                Idx[findNums[i]] = i;
            }
            
            // Result of N elements initialized to -1.
            vector<int> res(N, -1);
            
            stack<int> S;
            for (int x : nums) {
                
                // Start to pop and assign their next great number
                // if this element x is larger than stack top.
                //
                // E.g. x = 8;
                //      S = [9, 6, 5, 3]
                //
                // After this iteration, we have
                //      res[Idx(3)] = res[Idx(5)] = res[Idx(6)] = 8
                //      S = [9, 8]
                //
                while (!S.empty() && S.top() < x) {
                    auto Iter = Idx.find(S.top());
                    if (Iter != Idx.end())
                       res[Iter->second] = x;
                    S.pop();
                }
                
                // Keep pushing to the stack 
                // if numbers are in decreasing order.
                S.push(x);
            }
    
            return res;
        }````

Log in to reply
 

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