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

• 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;
}
};``````

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