参考文献
作者:Hasity
链接:https://www.acwing.com/solution/content/97229/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
C++ 代码
#include<iostream>
using namespace std;
const int N=1000010;
int a[N],s[N],head=0,tail=-1;
int main()
{
int n,k,num;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
//最小值
//单调递增队列
for(int i=0;i<n;i++)
{
//保证队列中的元素全部在窗口中
while(s[head]<i-k+1&&head<=tail)
{
head++;
}//如果队头划出窗口,去除
while (head<=tail&&a[i]<=a[s[tail]])//如果队列不为空或队列末尾元素大于当前元素,说明该队尾是无用的,因为在包含该队尾和当前元素的窗口中的最大值不会是队尾
{
tail--;
}
s[++tail]=i;//记录下标的好处是可以与当前位置比较来判断是否在窗口总
if(i>=k-1)
{
printf("%d ",a[s[head]]);
}
}
printf("\n");
//最大值
//单调递减队列
head=0;
tail=-1;
for(int i=0;i<n;i++)
{
//保证队列中的元素全部在窗口中
while(s[head]<i-k+1&&head<=tail)
{
head++;
}//如果队头划出窗口,去除
while (head<=tail&&a[i]>=a[s[tail]])//如果队列不为空或队列末尾元素小于当前元素,说明该队尾是无用的,因为在包含该队尾和当前元素的窗口中的最大值不会是队尾
{
tail--;
}
s[++tail]=i;//记录下标的好处是可以与当前位置比较来判断是否在窗口总
if(i>=k-1)
{
printf("%d ",a[s[head]]);
}
}
return 0;
}