C++ O(n log k) solution with heap ,but failed in the last test case,can anyone help?


  • 1
    V

    class Solution {

    public:

    void heapinsert(vector<int> &v,int a)
    {
        s++;
        v[s]=a;
        int i=s;
        while(i/2 && v[i/2]<v[i])
        {
            int tmp=v[i/2];
            v[i/2]=v[i];
            v[i]=tmp;
            i=i/2;
        }
        return;
    }
    
    void heapdelete(vector<int> &v,int a)
    {
        int i=1;
        for(i=1;i<=s;i++)
        if(v[i]==a)break;
        if(i==s)
        {
            s--;return;
        }
        int tmp=v[s];v[s]=v[i];v[i]=tmp;
        s--;
        while(2*i<=s)
        {
            int j=2*i;
            if(j+1<=s && v[j+1]>v[j])
            j=j+1;
            if(v[j]<=v[i])return;
            int tt=v[i];v[i]=v[j];v[j]=tt;
            i=j;
        }
        return;
        
    }
    
    
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        if(k<=0 || k>nums.size())return res;
        v.resize(k+1,0);
        for(int i=0;i<k;i++)
        {
            
            heapinsert(v,nums[i]);
        }
        for(int i=k;i<=nums.size();i++)
        {
            res.push_back(v[1]);
            if(i==nums.size())break;
            heapdelete(v,nums[i-k]);
            heapinsert(v,nums[i]);
        }
        return res;
    }
    
    vector<int> v;
    int s=0;
    

    };


  • 0
    S

    me too. Do u known why now?


Log in to reply
 

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