C++ O(NlogK) solution using Heap(Priority queue)


  • 2
    S
    typedef pair<int, int> Pair;
    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            vector<int> res;
            if(k ==0)   return res;
            priority_queue<Pair> Q;
            for(int i=0; i<k; i++){
                Q.push(Pair(nums[i], i));
            } 
            res.push_back(Q.top().first);
            for(int i=k; i<nums.size(); i++){
                while(!Q.empty() && Q.top().second <= i-k){
                    Q.pop();
                }
                Q.push(Pair (nums[i] , i));
                res.push_back(Q.top().first);
            }
            
            return res;
        }
    };

  • 0
    M

    That's not O(N), not even O(N log K), but O(N log N).


  • 0
    S
    This post is deleted!

  • 0
    S

    why not O(NlogK)? I saw N Heap sort with size K.


  • 0
    M

    Because this solution's priority queue can grow to size N, even when k=2.


Log in to reply
 

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