【题目描述：】
有一个 1 ∗ n 的矩阵，有 n 个正整数。
现在给你一个可以盖住连续的 k 的数的木板。
一开始木板盖住了矩阵的第 1 ∼ k 个数，每次将木板向右移动一个单位，直到右端与第 n 个数重合。
每次移动前输出被覆盖住的最大的数是多少。
【输入格式：】
第一行两个数，n，k，表示共有 n 个数，木板可以盖住 k 个数。
第二行 n 个数，表示矩阵中的元素。
【输出格式：】
共 n − k + 1 行，每行一个正整数。
第 i 行表示第 i ∼ i + k − 1 个数中最大值是多少。
[算法分析：]
这道题是可以用st表做区间RMQ的，但也可以用单调队列.
st表复杂度为预处理的\(O(n log_2 n)\)，
而单调队列的复杂度为\(O(n)\)（有一些省略掉的常数）
使用双端队列容器\(deque\)便于维护序列的单调性，
由于是每次输出最大值，所以从队尾将所有小于要加入元素\(a\)的值都\(pop\)掉，再把a push_back()进去
现在考虑如何取出多余的队首：
比如已经开始找区间\([3,\ 5]\)的最值了，第二个元素就是多余的
使用一个结构体存储元素的数值和位置，如果这个元素的位置加上\(k\)比当前的\(i\)还要小，则pop_front()
\([Code:]\)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;const int MAXN = 2e6 + 1;int n, k;
int a[MAXN];
struct Node {
int v, pos;
};deque<Node> q;inline int read() {
int x=0, f=1; char ch=getchar();
while(ch<'0' || ch>'9') {
if(ch == '-') f = -1;
ch = getchar();
}
while(ch>='0' && ch<='9')
x=(x<<3)+(x<<1)+ch-48, ch=getchar();
return x * f;
}int main() {
n = read(), k = read();
for(int i=1; i<=n; ++i) a[i] = read();
//先将前k个元素加入队列
for(int i=1; i<=k; ++i) {
while(!q.empty() && q.back().v < a[i]) q.pop_back();
q.push_back((Node){a[i], i});
}
printf("%d\n", q.front().v);
for(int i=k+1; i<=n; ++i) {
while(!q.empty() && q.back().v < a[i]) q.pop_back();
q.push_back((Node){a[i], i});
while(q.front().pos + k <= i) q.pop_front();
printf("%d\n", q.front().v);
}
}
