比较投机取巧了/流汗黄豆

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n,k; cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++) cin>>a[i];
    int sho[10002],d=0;;
    int i;
    for(i=0;i<n;i++){
        if(i+k<=n){
            vector<int> v(a+i,a+i+k);
            sort(v.begin(),v.end());
            cout<<v.back()<<' ';
            sho[d++]=v.front();
        }else break;
    }
    cout<<endl;
    for(int i=0;i<d;i++) cout<<sho[i]<<' ';
    return 0;
}

https://blog.csdn.net/ljd201724114126/article/details/80663855
分享一个讲单调队列的博客，我觉得挺好的。

//#include "stdafx.h"
#include<iostream>
//#include<cstdio>
using namespace std;
//变参考边实现单调队列
#define N 100010
struct node
{
int x,y;
}v[N];//V是用数组模拟的队列

int a[N];
int mi[N],n;
int mx[N],m;

void getmin();
void getmax();

int main()
{
int i,j;
cin>>n>>m;//10 3
// m是队列的长度/区间
for(i=1; i<=n; i++)

cin>>a[i];//6 4 10 10 8 6 4 2 12 14
getmin();
getmax();
for(i=1; i<=n-m+1; i++)
cout<<mx[i]<<" ";
cout<<endl;
for(i=1; i<=n-m+1; i++)
cout<<mi[i]<<" ";
return 0;
}
void getmax()//单调增队列
{
int head=1,tot=0,i;//head队首指针，tot队尾指针

for(i=1; i<m; i++)//队列的初始化:前m-1个先直接进入队列
{
while(head<=tot && v[tot].x <=a[i])
tot--;
v[++tot].x =a[i],v[tot].y =i;
}
for( ; i<=n; i++)
{
while(head<=tot && v[tot].x <=a[i])//将a[i]从队尾元素开始进行比较
tot--;
v[++tot].x =a[i],v[tot].y =i;//将a[i]插入队列，并记录其下标
//先插入
//再维护其长度
while(v[head].y <i-m+1)//要保证队列里的元素不超过m个
head++;
mx[i-m+1]=v[head].x ;//将队首元素的值存起来
}//i-m+1是保证队列里有m个元素
}
/*
//6 4 10 10 8 6 4 2 12 14
首先插入6，用(6,0)表示
第二步：插入(4,1):队列为：(6,0)(4,1)
第三步：队列为：(10,2)
第四步：队列为：(10,3)
第五步：队列为：(10,3)(8,4)
第六步：队列为：(10,3)(8,4)(6,5)
第七步：队列为：(8,4)(6,5)(4,6)
第八步：队列为：(6,5)(4,6)(2,7)
第九步：队列为：(12,8)
最后一步步：队列为：(14,9)
最后的答案为每一步的首元素
*/
void getmin()
{
int hd=1,totil=0,i;
for(i=1; i<m; i++)
{
while(hd<=totil && v[totil].x >=a[i])
totil--; //数组最前面的数是最小值，最后面的是最大值
v[++totil].x =a[i];v[totil].y=i;//将前m-1先放进队列
}
for(; i<=n; i++)//i从m之后开始
{
while(hd<=totil && v[totil].x >=a[i])
totil--;
v[++totil].x =a[i];
v[totil].y =i;
while( v[hd].y <i-m+1)
hd++;//把已经超出范围的从头部排除
mi[i-m+1]=v[hd].x;//将最小值存起来
}
}