单调队列,保证当前队列的头元素是最大的(后面的可以<=当前的头元素),移除窗口元素时,比较是否跟队列头相等即可
-
vector<int> maxSlidingWindow(vector<int>& nums, int k){
-
vector<int> res;
-
deque<int> q;
-
int len = nums.size();
-
if(len ==0) return res;
-
for(int i=0;i<len;++i){
-
for(;i>0&&q.size()>0&&nums[i]>q.back();) q.pop_back();
-
q.push_back(nums[i]);
-
if(i>=k &&nums[i-k]==q.front()) q.pop_front();
-
if(i >=k-1) res.push_back(q.front());
-
}
-
return res;
-
}
阅读(860) | 评论(0) | 转发(0) |