深圳企业网站建设服务平台_网红营销网站_博客推广工具_seo网上培训多少钱

#include <bits/stdc++.h>
using namespace std;const int N =1e6+10;
int n,k;
int a[N];int q[N],hh,tt;int main()
{scanf("%d%d",&n,&k);for(int i = 0; i < n; i++){scanf("%d",&a[i]);if(i-k+1 <0){while(hh!=tt &&a[q[tt-1]]>=a[i]){tt--;}q[tt++]=i;}else{if(hh!=tt && i-k+1 > q[hh]){hh++;}while(hh!=tt &&a[q[tt-1]]>=a[i]){tt--;}q[tt++]=i;printf("%d ",a[q[hh]]);}}printf("\n");hh=0,tt=0;for(int i = 0; i < n; i++){if(i-k+1 <0){while(hh!=tt &&a[q[tt-1]]<=a[i]){tt--;}q[tt++]=i;}else{if(hh!=tt && i-k+1 > q[hh]){hh++;}while(hh!=tt &&a[q[tt-1]]<=a[i]){tt--;}q[tt++]=i;printf("%d ",a[q[hh]]);}}return 0;
}

n个数的数组，取k的区间，求每个区间最小值和最大值

说的是单调队列，但是除了头删外还要尾删，所以stl的队列用不了

单调队列里保存的是下一个区间可能的目标值。拿最小值为例，加入数x，那么单调队列中大于x的数最后一定不可能是目标值，所以直接删掉，单调正是这样不知不觉形成的

在这个过程要注意把单调队列中不符合k区间的下标先删去，再去加x

这道题卡时间，用cout没过用printf过了