洛谷 P1440 求m区间内的最小值
题目描述
一个含有 n 项的数列，求出每一项前的 m 个数到它这个区间内的最小值。若前面的数不足 m 项则从第 1 个数开始，若前面没有数则输出 0。
输入格式
第一行两个整数，分别表示 n，m。
第二行，n 个正整数，为所给定的数列 ai。
输出格式
n 行，每行一个整数，第 i 个数为序列中 ai 之前 m 个数的最小值。
输入输出样例
输入 #1复制
6 2 7 8 1 4 3 2
输出 #1复制
0 7 7 1 1 3
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6+10;
int q[N];
int a[N];
int n,m;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
int hh = 1,tt = 0;//hh队头 tt队尾
for(int i=1;i<=n;i++) {
cout<<a[q[hh]]<<endl;//队头元素就是最小值
while(hh<=tt && a[q[tt]]>a[i]) tt--;//维护单调队列 队列中的元素单调递增
if(hh<=tt && i - m + 1 > q[hh]) hh++;//滑出窗口 就然队头前进
q[++tt] = i;
}
}