Simple C++ Solution O(n) Time O(1) Extra Space (No Stack, using output array only)


  • 0
    F
    class Solution {
    public:
        vector<int> nextGreaterElements(vector<int>& nums) {
            int n = nums.size();
            vector<int> result(n);
            if (n <= 0) return result;
            result.back() = -1;
            if (n <= 1) return result;
            for (int i = 2*n - 2; i >= 0; --i)
            {
                int j = i + 1;
                while (j != -1 && nums[i % n] >= nums[j % n])
                    j = result[j % n];
                result[i % n] = j % n;
            }
            for (auto & i : result)
                i = i == -1 ? -1 : nums[i];
            return result;
        }
    };
    

Log in to reply
 

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