使用的队列是一个假队列,即本题使用的队列可以从尾部出队(为了使这个假队列满足严格单调性)
最小值的四个步骤:
1. 当前队头元素(即在某个窗口为最小值),在当前值入队时,是否还出现在窗口中
如不应该出现(即窗口放不下了 k值约束
),则调整队头,使队头元素出现在窗口中
此时当前值为a[6]时,队头元素a[3]显然对只显示3个元素的窗口来说放不下,故调整队头为q[hh] = 5
就是队头元素为a[5]
2. 判断当前值入队前 队列中在以后没有用的值,即把从队尾开始把满足a[q[tt]] >= a[i]
的值从队列剔除,因为只要有a[i]在,a[q[tt]]就永远不可能为最小值(嗯哼)。
3. 将当前值入队q[++tt] = i
,为了以后其有朝一日成为最小值
4. 输出队头元素,即严格单调递增又在当前窗口的最小值。
最大值的四个步骤:
就是把上面步骤2中的a[q[tt]] >= a[i]
改为a[q[tt]] <= a[i]
因为要使这个假队列满足严格单调递减
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
/**
* 此题不是真正的队列,即可以从尾部剔除队列的元素值,使其满足单调性
*/
int a[N], q[N]; //a存原数组, q存单调队列
int hh, tt; //队列的头部和尾部
int n, k;
int main()
{
cin>>n>>k;
for(int i = 0; i < n; ++i)
scanf("%d", &a[i]);
hh = 0; tt = -1; //初始化
for(int i = 0; i < n; ++i)
{
//step1、查看当前队头元素是否还在窗口中,若不是则去掉队头元素,
//使队头元素满足在窗口中
if(hh <= tt && q[hh] < i-k+1) hh++;
//step2、查看当前窗口的前两个元素较当前a[i]的大小
//若a[q[tt]] >= a[i] 则队尾元素剔除----->此处队列不是严格队列,尾部不仅可以入队,还可以从尾部出队,
//一直到a[q[tt]] < a[i],即使队列满足严格单调递增
while(hh <= tt && a[q[tt]] >= a[i]) tt--;
//如果当前窗口前两个元素都a[q[tt]] >= a[i]的话
//则当前窗口的最小值为a[i] ,故将该值入队
q[++tt] = i;
//当前窗口的队头元素为该窗口三个元素的最小值
//同时窗口元素个数要满足 == k
if(i >= k-1) printf("%d ", a[q[hh]]);
// if(hh == i-k+1) printf("%d ", a[q[hh]]);
}
puts("");
hh = 0; tt = -1; //初始化
for(int i = 0; i < n; ++i)
{
//step1、查看当前队列头部元素是否还在窗口中,若不是则去掉队头元素,
//使队头元素满足在窗口中
if(hh <= tt && q[hh] < i-k+1) hh++;
//step2、查看当前窗口的前两个元素较当前a[i]的大小
//若a[q[tt]] <= a[i] 则队尾元素出队,
//一直到a[q[tt]] > a[i], 即使队列满足严格单调递减
while(hh <= tt && a[q[tt]] <= a[i]) tt--;
//如果当前窗口前两个元素都a[q[tt]] >= a[i]的话
//则当前窗口的最小值为a[i] ,故将该值入队
q[++tt] = i;
//当前窗口的队头元素为该窗口三个元素的最小值
//同时窗口元素个数要满足 == k
if(i >= k-1) printf("%d ", a[q[hh]]);
}
puts("");
return 0;
}