【题解】P2032

P2032

题目

题目描述：

有一个 $1 \times n$ 的矩阵，有 $n$ 个整数。

现在给你一个可以盖住连续 $k$ 个数的木板。

一开始木板盖住了矩阵的第 $1 \sim k$ 个数，每次将木板向右移动一个单位，直到右端与第 $n$ 个数重合。

每次移动前输出被覆盖住的数字中最大的数是多少。

输入格式：

第一行两个整数 $n,k$，表示共有 $n$ 个数，木板可以盖住 $k$ 个数。

第二行 $n$ 个整数，表示矩阵中的元素。

输出格式：

共 $n - k + 1$ 行，每行一个整数。

第 $i$ 行表示第 $i \sim i + k - 1$ 个数中最大值是多少。

数据范围与说明：

对于 $20\%$ 的数据，$1 \leq k \leq n \leq 10^3$。

对于 $50\%$ 的数据，$1 \leq k \leq n \leq 10^4$。

对于 $100\%$ 的数据，$1 \leq k \leq n \leq 2 \times 10^6$，矩阵中的元素大小不超过 $10^4$ 并且均为正整数。

输入输出样例 #1

输入：

5 3
1 5 3 4 2

输出：

5
5
4

代码

#include <bits/stdc++.h>
using namespace std;
int q[2000006];
int a[2000006];
int main(){
    int n,k;
    cin>>n>>k;
    int left=1;
    int right=1;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    q[1]=1;
    for(int i=1;i<=n;i++){
        if(q[left]<=i-k){
            left++;
        }
        while(left<=right&&a[q[right]]<=a[i]){
            right--;
        }
        q[++right]=i;
        if(i>=k){
            printf("%d\n",a[q[left]]);
        }
    }
    return 0;
}