题目描述
一个含有n项的数列(n<=2000000)，求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始，若前面没有数则输出0。
输入格式：
第一行两个数n，m。
第二行，n个正整数，为所给定的数列。
输出格式：
n行，第i行的一个数ai，为所求序列中第i个数前m个数的最小值。
输入样例#1：
6 2 7 8 1 4 3 2
输出样例#1：
0 7 7 1 1 3
单调队列模板题
用一个队列维护第i个数前m个最小值的位置
注意在判断的时候要保持队列非空，否则会导致在队列为空的时候队首提前
#include<bits/stdc++.h> using namespace std; #define maxn 2000005 int a[maxn],q[maxn]; int n,m,l=1,r; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } for(int i=1;i<=n;i++){ printf("%d\n",a[q[l]]); if(i-q[l]+1>m&&l<=r)l++; while(a[i]<a[q[r]]&&l<=r)r--; q[++r]=i; } return 0; }
原文：http://www.cnblogs.com/Elfish/p/7634319.html