洛谷：用单调队列解 P2032 扫描

传送门：P2032 扫描 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P2032

题目描述

有一个 1 \times n1×n 的矩阵，有 nn 个整数。

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

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

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

输入格式

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

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

输出格式

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

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

输入输出样例

输入 #1复制

5 3
1 5 3 4 2

输出 #1复制

5
5
4

说明/提示

对于 20\%20% 的数据，1 \leq k \leq n \leq 10^31≤k≤n≤103。

对于 50\%50% 的数据，1 \leq k \leq n \leq 10^41≤k≤n≤104。

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

求解步骤和思路请参考求m区间内的最小值或滑动窗口：

洛谷：P1440 求m区间内的最小值_´悠 子ᴗ`-_-╭☞ꪗꪖꪑ的博客-CSDN博客用单调队列来求解求m区间内的最小值https://blog.csdn.net/qq_66500237/article/details/127797778?utm_source=app&app_version=5.5.0&code=app_1562916241&uLinkId=usr1mkqgl919blen

或：

洛谷：P1886 滑动窗口 /【模板】单调队列题解_´悠 子ᴗ`-_-╭☞ꪗꪖꪑ的博客-CSDN博客用单调队列求解移动窗口https://blog.csdn.net/qq_66500237/article/details/127803829

代码：

#include<iostream>
using namespace std;
int q[2000005],a[2000005],n,k,front=1,rear=0;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		while(q[front]<=i-k&&front<=rear)front++;
		while(front<=rear&&a[q[rear]]<=a[i])rear--;
		q[++rear]=i;
		if(i>=k)cout<<a[q[front]]<<"\n";
	}
	return 0;
}