单调队列和单调栈问题优化思路:
栈/队列里面有没有元素是没有用的,有的话想办法删掉,使队列保持单调性
然后再在单调的队列里面查找某一特定值
#include<iostream>
using namespace std;
const int N = 1e6+10;
int a[N],q[N];
int n,k;
int main(){
cin>>n>>k;
for(int i=0;i<n;i++) scanf("%d", &a[i]);
// for(int i=0;i<n;i++) printf("%d ", 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) printf("%d ", a[q[hh]]);//输出队头元素
}
puts("");
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) printf("%d ", a[q[hh]]);//输出队头元素
}
return 0;
}