题意:
思路:用单调队列去不断进行筛数操作,O(n)扫一遍,两个while第一个while是使队列是单调的,如果不符合就弹数,第二个while是使队列里的元素要满足前m个。
#include<bits/stdc++.h> using namespace std; const int maxn=2e6+100; int a[maxn]; deque<int >m1; int main() { int n,m; scanf("%d%d",&n,&m); printf("%d\n",0); for(int i=1;i<n;i++){ scanf("%d",&a[i]); while(m1.size()&&a[m1.back()]>a[i]){ m1.pop_back(); } m1.push_back(i); while(i-m>=m1.front()){ m1.pop_front(); } printf("%d\n",a[m1.front()]); } return 0; }