C++ O(n) solution with self-defined queue


  • 0
    E

    The core idea is to save the max value after "point i". With the class myQueue, the algorithm is clear. Each element will push (pop) in (from) the queue only once, so the complexity is linear.

    class myQueue {
    public:
    	myQueue(int len = 1) : que(vector<int>(len, 0)), bg(0), ed(0), l(len) {}
    	bool empty() { return bg == ed; }
    	int  top() { return empty() ? -1 : que[bg]; }
    	void push(int val)
    	{
    		if(ed >= l)
    			return;
    		if(!empty())
    		{
    			for(int i=ed-1; i>=bg; --i)
    				if(que[i] < val)
    					que[i] = val;
    				else
    					break;
    		}
    		que[ed] = val;
    		++ed;
    	}
    	void pop(){ if(!empty()) ++bg; }
    	int  size() { return ed - bg; }
    	void print()
    	{
    		for (int i=bg; i<ed; ++i)
    			cout << que[i] << " ";
    		cout << endl;
    	}
    private:
    	vector<int> que;
    	int bg, ed, l;
    };
    
    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    		int len = nums.size();
    		vector<int> ret;
    		if(len == 0)
    			return ret;
    		myQueue mq(len);
    		for(int i=0; i<k; ++i)
    			mq.push(nums[i]);
    		ret.push_back(mq.top());
    		for(int i=k; i<len; ++i)
    		{
    			mq.pop();
    			mq.push(nums[i]);
    			ret.push_back(mq.top());
    		}
    		return ret;
        }
    };

Log in to reply
 

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