最开始做的时候,暴力解法结果不管怎么剪枝,还是超时了。
后来看到了卡哥的方法,学到了单调队列,其实就是自定义队列。用deque来实现。
有三个关键点:pop,push,front.
pop,如果遍历的元素等于队头元素,则头删。
push,把比遍历元素小的都进行尾部删。
front,就是普通的查找队头。
循环遍历的时候不断调用这些函数即可。
点击查看代码
class Solution {
public:
void m_pop(deque<int>&q,int val){
if(!q.empty()&&q.front()==val){
q.pop_front();
}
}
void m_push(deque<int>&q,int val){
while(!q.empty()&&q.back()<val){
q.pop_back();
}
q.push_back(val);
}
int m_max(deque<int>&q){
return q.front();
}
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int>q;
vector<int>cnt;
int left=0;int right=k;
for(int i=0;i<k;i++){
m_push(q,nums[i]);
}
cnt.push_back(m_max(q));
while(right<nums.size()){
m_pop(q,nums[left]);
m_push(q,nums[right]);
cnt.push_back(m_max(q));
++left;
++right;
}
return cnt;
}
};