【题目描述:】
有一个 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());
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());
}
}
原文:https://www.cnblogs.com/devilk-sjj/p/9073774.html