题目描述
一个含有n项的数列(n<=2000000)，求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始，若前面没有数则输出0。
输入输出格式
输入格式：
第一行两个数n，m。
第二行，n个正整数，为所给定的数列。
输出格式：
n行，第i行的一个数ai，为所求序列中第i个数前m个数的最小值。
思路：单调队列
#include <bits/stdc++.h> using namespace std; const int maxn = 2e6 + 5; int a[maxn]; int main() { int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); } deque<int> q; printf("0\n"); q.push_back(1); for(int i = 2; i <= n; i++) { while(!q.empty() && q.front() < i - m) { // 当前队头元素不在窗口范围，弹出 q.pop_front(); } while(!q.empty() && a[q.back()] >= a[i]) { // 当前队尾元素比当前元素小，弹出（当前元素比队尾元素更优） q.pop_back(); } printf("%d\n", a[q.front()]); q.push_back(i); } return 0; }
