O(n) C++ solution with explanation


  • 0
    G

    The idea is to iterate backward starting from the last element. Maintain a stack which will give us the visited elements in the increasing order. So when we visit an element, if the top of the stack is greater then that's the answer for that element (remember this in a map for constructing the solution at the end). If the top of the stack is smaller then pop until otherwise or stack become empty. Push the current element into stack always since it will always be smaller than the stack top.

        vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
            stack<int> my_stack;
            map<int, int> my_map;
            for (int i = nums.size() - 1; i >= 0; i--) {
                int n = nums[i];
                if (my_stack.empty() || my_stack.top() < n) {
                    while (!my_stack.empty() && my_stack.top() < n) my_stack.pop();
                }
                my_map[n] = my_stack.empty() ? -1 : my_stack.top();
                my_stack.push(n);
            }
            vector<int> ans;
            for (auto n : findNums) {
                ans.push_back(my_map[n]);
            }
            return ans;
        }
    

Log in to reply
 

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