C++ from O(n^2) to O(n)


  • 0

    Solution 1

    Brute force, O(n^2)

    class Solution {
    public:
        vector<int> nextGreaterElements(vector<int>& nums) {
            int n = nums.size();
            vector<int>res;
            for(int i = 0; i < nums.size(); i++){
                int j = (i + 1) % n;
                while(j != i){
                    if(nums[j] > nums[i]) break;
                    ++j %= n;
                }
                res.push_back(j == i ? -1 : nums[j]);
            }
            return res;
        }
    };
    

    Solution 2

    Using a stack and a deque, O(n)

    class Solution {
    public:
        vector<int> nextGreaterElements(vector<int>& nums) {
            vector<int>res(nums.size(), -1);
            stack<int>s; // decreasing sequence
            deque<int>q; // Increasing sequence
            for(int i = 0; i < nums.size(); i++){
                if(q.empty() || nums[i] > q.back()) q.push_back(nums[i]);
                while(!s.empty() && nums[i] > nums[s.top()]){
                    res[s.top()] = nums[i];
                    s.pop();
                }
                s.push(i);
            }
            while(!s.empty()){
                while(!q.empty() && nums[s.top()] >= q.front()) q.pop_front();
                if(!q.empty()) res[s.top()] = q.front();
                s.pop();
            }
            return res;
        }
    };
    

Log in to reply
 

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