7935: 最大值问题 单调队列

描述

给定n个正整数，crq先选了第1~k个数，要求yuyu求出最大值，yuyu轻松完成，crq直接甩出一堆，要求第2~k+1个，3~k+2个, ..., n-k+1~n个，全部都求出来，之后便轻松休息了。

输入

第一行两个整数 n和k（1≤k≤n≤10⁶）。

第二行 n个整数，表示编号1~n方格中的数字a_i（1≤a_i≤3×10⁷）。

输出

按顺序求出各个最大值，每行输出一个。

样例输入

5 3
1 2 3 4 5

样例输出

3
4
5

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10,inf = 0x3f3f3f3f;
int gcd(int a,int b){return a==0?b:gcd(b%a,a);}
int a[N],q[N];
int n,k;
void getmax()
{
    int head = 0,tail = 0;
    for(int i=1;i<k;i++)
    {
        while(head<=tail && a[q[tail]]<=a[i])tail--;
        q[++tail] = i;
    }
    for(int i=k;i<=n;i++)
    {
        while(head<=tail && a[q[tail]]<=a[i])tail--;
        q[++tail] = i;
        while(q[head]<=i-k)head++;
        printf("%d\n",a[q[head]]); 
    }
    
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    getmax();
     return 0;
}