维护一个窗口和一个双端队列
窗口的左端点为L,右端点为i,一开始L和i都是0,让i从0开始滑动,在此期间维护一个双端队列qmax
i向右移动,代表往窗口中加入数据:
如果nums[i] < qmax的尾部数据,则i这个下标直接从尾部进入双端队列
如果nums[i] > qmax的尾部数据,则qmax的尾部一直出队,知道队为空或者队尾小于nums[i]
deque<int> qmax; // 最大值双端队列,保存的是下标 int L = 0; // 窗口左端点 for(int i = 0;i<num.size();i++){ while(!qmax.empty() && num[qmax.back()] <= num[i]){ qmax.pop_back(); }
当形成长度为size的窗口时,L开始移动,代表从窗口中删除数据:
对比L-1与qmax的队头,如果相等,则队头出队(表示这个数已经被剔除了)
if( i >= size - 1){//如果形成了窗口 ans.push_back(num[qmax.front()]); L ++; if(qmax.front() == L-1){ qmax.pop_front(); } }
完整代码:
class Solution { public: vector<int> maxInWindows(const vector<int>& num, unsigned int size) { vector<int> ans; if(num.empty() || size < 1 || num.size() < size){ return ans; } deque<int> qmax; // 最大值双端队列,保存的是下标 int L = 0; // 窗口左端点 for(int i = 0;i<num.size();i++){ while(!qmax.empty() && num[qmax.back()] <= num[i]){ qmax.pop_back(); } qmax.push_back(i); if( i >= size - 1){//如果形成了窗口 ans.push_back(num[qmax.front()]); L ++; if(qmax.front() == L-1){ qmax.pop_front(); } } } return ans; } };
整个过程就是将窗口的右端点一直推到数组的最后一个位置,所以时间复杂度是o(n)