C++ O(n) time and O(1) space without stack


  • 0
    T
    vector<int> nextGreaterElements(vector<int>& nums) 
        {
            vector<int> result(nums.size(), -1);
            if (nums.size() <= 1)
                return result;
            int maxIndex = 0;
            for (int i = 1; i < nums.size(); i++)
                maxIndex = nums[maxIndex] > nums[i] ? maxIndex : i;
            for (int i = 1; i < nums.size(); i++)
            {
                int j = (maxIndex - i + nums.size()) % nums.size();
                int p = (j + 1) % nums.size();
                while (p != -1 && nums[j] >= nums[p])
                {
                    p = result[p];
                }
                if (p != -1)
                    result[j] = p;
            }
            for (int i = 0; i < result.size(); i++)
                if (result[i] != -1)
                    result[i] = nums[result[i]];
            return result;
        }
    

Log in to reply
 

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