23-单调队列-滑动窗口

题目

来源

154. 滑动窗口 - AcWing题库

思路

详见代码

代码

/*
构造单调队列进行优化，思路与单调栈的思路类似
--
队列来维护窗口：新元素插入到队尾，旧元素从队头移除
如果暴力去实现的话，就是暴力去遍历队列中的所有元素，
计算出相应的最大值和最小值；时间复杂度为o(nk)
--
最小值求解：
3,-1,-3：只要-3存在，那么3,-1一直都不会当最小值输出
其实就是删除逆序对；使之成为严格单调上升的队列；
最小值为相应的队头元素
--
最大值同理
*/#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],q[N];//队列存储的是相应的下标int main(){int n,k;cin>>n>>k;for(int i=0;i<n;i++){cin>>a[i];}//寻找最小值int hh=0,tt=-1;for(int i=0;i<n;i++){if(hh<=tt && i-k+1>q[hh])hh++;//旧元素滑出窗口了，从队头删掉while(hh<=tt && a[q[tt]]>=a[i])tt--;//因为是插入在队尾，所以队尾元素要是比当前的大，就可以删掉q[++tt]=i;if(i>=k-1)cout<<a[q[hh]]<<" ";}cout<<endl;//寻找最大值hh=0,tt=-1;for(int i=0;i<n;i++){if(hh<=tt && i-k+1>q[hh])hh++;//旧元素滑出窗口了，从队头删掉while(hh<=tt && a[q[tt]]<=a[i])tt--;//因为是插入在队尾，所以队尾元素要是比当前的大，就可以删掉q[++tt]=i;if(i>=k-1)cout<<a[q[hh]]<<" ";}return 0;
}