C++ O(n) using priority queue + map. 72ms


  • 0
    I

    First time posting and definitely still learning, but wanted to share! Priority_Queue + map in O(n) time - 72ms.

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> results;
        if (nums.size() == 0) return results;
        unordered_map<int, int> toIgnore;
        priority_queue<int, vector<int>> pq;        
        int i = 0;
        for (/* No 1st */; i < k; i++) pq.push(nums[i]);
        while (i <= nums.size()) 
        {
            if (toIgnore.empty()) results.push_back(pq.top());
            else 
            {
                while (toIgnore.find(pq.top()) != toIgnore.end()) 
                {
                    toIgnore[pq.top()]--;
                    if (toIgnore[pq.top()] == 0) toIgnore.erase(pq.top());
                    pq.pop();
                }
                results.push_back(pq.top());
            }
            
            if (nums[i - k] == pq.top()) 
            {
                pq.pop();
            }
            else 
            {
                toIgnore[nums[i - k]]++;
            }
            if ( i < nums.size()) pq.push(nums[i]);
            i++;            
        }       
        return results;
        }
    };

Log in to reply
 

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