模板:遞增隊(duì)列或是遞減隊(duì)列只需要修改刪除隊(duì)尾元素的判斷條件即可洞翩。
原理 以遞增隊(duì)列舉例:
以一個(gè)長(zhǎng)度為k的移動(dòng)窗口從k處開(kāi)始移動(dòng)座舍,遍歷數(shù)組中的每個(gè)元素沮翔,添加到隊(duì)列末尾并且于前一個(gè)元素相比較,直到有一個(gè)元素大于當(dāng)前元素曲秉,退出循環(huán)采蚀,將當(dāng)前元素加入隊(duì)列,并且將位置坐標(biāo)另記入一個(gè)位置數(shù)組承二。尋找k長(zhǎng)度窗口內(nèi)的最大值則只需要在位置數(shù)組遍歷榆鼠,第一個(gè)大于等于i的就是所求的最大值。
···
include<iostream>
include<cstdio>
include<cstring>
include<string>
include<queue>
include<map>
include<vector>
include<algorithm>
include<stack>
include<set>
using namespace std;
typedef long long ll;
const int N=1000010;
const int inf=0x3f3f3f;
int n,k;
int q[N],mk[N],a[N];
void qmax()
{
int i,st=1,tt=1;
for(i=1;i<=n;i++)
{
while(tt<st&&q[st-1]<=a[i]) st--;
q[st]=a[i];mk[st]=i;st++;
if(i>=k)
{
while(tt<st&&mk[tt]<=i-k) tt++;
printf("%d ",q[tt]);
}
}
}
void qmin()
{
int i,st=1,tt=1;
for(i=1;i<=n;i++)
{
while(tt<st&&q[st-1]>=a[i]) st--;
q[st]=a[i];mk[st]=i;st++;
if(i>=k)
{
while(tt<st&&mk[tt]<=i-k) tt++;
printf("%d ",q[tt]);
}
}
}
int main() {
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
qmin();
printf("\n");
qmax();
printf("\n");
return 0;
}···