给定一个n个数的数列，从左至右输出每个长度为m的数列段内的最大数。
输入：第一行两个整数n和m( 1<= n <= 20 0000,m<=n）。下来给出n个整数。
输出：一行一个整数，表示每连续m个数的最大值。
样例输入：
8 3
1 3 -1 -3 5 3 6 7
样例输出：
3
3
5
5
6
7
维护一个单调队列，列内严格递减。若是首端元素已经脱离当前M个元素的区间，则去除。若是新元素比队尾元素严格小，直接入队，否则元素出队至合格后，新元素入队。比较模板了：
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define pb push_back
#define fi first
#define se second const double eps=1e-, PI=acos(-1.0f);
const int inf=0x3f3f3f3f;
const int maxN=2e5+;
int N, M, K, T;
int g[maxN];
deque<pii> dq; int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
scanf("%d%d", &N, &M);
for (int i = ; i <= N; ++i)
scanf("%d", &g[i]);
for (int i = ; i <= N; ++i) {
while (dq.size() && dq.back().fi <= g[i])
dq.pop_back();
dq.push_back(pii(g[i], i));
while (dq.back().se - dq.front().se + > M)
dq.pop_front();
if (i >= M)
printf("%d\n", dq.front().fi);
}
return ;
}
用数组实现deque，得交c++，G++会TLE
#include <stdio.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define maxN 1000005
int n, k, t, ab[maxN], as[maxN];
int lb, rb, ls, rs;
struct node{int v, i;} a, B[maxN], S[maxN]; int main () {
//freopen("data.in", "r", stdin);
scanf("%d%d", &n, &k);
lb = rb = ls = rs = ;
FOR(i, , n) {
scanf("%d", &a.v), a.i = i;
while (ls < rs && S[rs - ].v >= a.v) rs--;
S[rs++] = a;
if (S[ls].i <= i - k) ++ls;
if (i >= k) ab[i] = S[ls].v; while (lb < rb && B[rb - ].v <= a.v) rb--;
B[rb++] = a;
if (B[lb].i <= i - k) ++lb;
if (i >= k) as[i] = B[lb].v;
}
FOR(i, k, n) printf(i == k ? "" : " "), printf("%d", ab[i]);
puts("");
FOR(i, k, n) printf(i == k ? "" : " "), printf("%d", as[i]);
return ;
}