单调栈（G - Sliding Window POJ - 2823 ）

题目链接：https://cn.vjudge.net/contest/276251#problem/G

STL AC代码（耗时：10985s）：

 #include<iostream>

 #include<stack>

 #include<cmath>

 #include<string>

 #include<stdio.h>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 using namespace std;

 # define inf 0x3f3f3f3f

 # define ll long long

 const int maxn = 1e6+;

 int minn[maxn],maxx[maxn],sto[maxn];

 inline int read1()

 {

     int f=,x=;

     char s=getchar();

     while(s<'' || s>'')

     {

         if(s=='-')

             f=-;

         s=getchar();

     }

     while(s>='' && s<='')

     {

         x=x*+s-'';

         s=getchar();

     }

     return x*f;

 }

 int main()

 {

     int n,m;

     n=read1();

     m=read1();

     // scanf("%d %d",&n,&m);

     deque<int>q1;

     deque<int >q2;

     int tot=,tmp;

     for(int i=;i<=n;i++){

     sto[i]=read1();

     }

     for(int i=; i<=n; i++)

     {

         while(!q1.empty()&&q1.front()<i-m+)//先判断左边界有没有超出范围

             q1.pop_front();

         while(!q1.empty()&&sto[i]<sto[q1.back()])//保持队列单调递增

         {

             q1.pop_back();

         }

         q1.push_back(i);

         if(i>=m)

             minn[++tot]=q1.front();

         while(!q2.empty()&&q2.front()<i-m+)

             q2.pop_front();

         while(!q2.empty()&&sto[i]>sto[q2.back()])

         {

             q2.pop_back();

         }

         q2.push_back(i);

         if(i>=m)

             maxx[tot]=q2.front();

     }

     for(int i=; i<=tot; i++)

     {

         if(i==)

             printf("%d",sto[minn[i]]);

         else

             printf(" %d",sto[minn[i]]);

     }

     printf("\n");

     for(int i=; i<=tot; i++)

     {

         if(i==)

             printf("%d",sto[maxx[i]]);

         else

             printf(" %d",sto[maxx[i]]);

     }

     printf("\n");

     return ;

 }

数组模拟（耗时：7152ms）AC代码：

 #include<iostream>

 #include<stack>

 #include<cmath>

 #include<string>

 #include<stdio.h>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 using namespace std;

 # define inf 0x3f3f3f3f

 # define ll long long

 const int maxn = 1e6+;

 int minn[maxn],maxx[maxn],sto[maxn];

 int moni[maxn];

 inline int read1()

 {

     int f=,x=;

     char s=getchar();

     while(s<'' || s>'')

     {

         if(s=='-')

             f=-;

         s=getchar();

     }

     while(s>='' && s<='')

     {

         x=x*+s-'';

         s=getchar();

     }

     return x*f;

 }

 int main()

 {

     int n,m;

     n=read1();

     m=read1();

     int l=,r=;

     int tot=;

     for(int i=; i<=n; i++)

     {

         sto[i]=read1();

     }

     for(int i=; i<=n; i++)

     {

         while(l<=r&&moni[l]<i-m+)

             l++;

         while(l<=r&&sto[i]<sto[moni[r]]){

             r--;

         }

              moni[++r]=i;

         if(i>=m)

             minn[++tot]=moni[l];

     }

     l=,r=,tot=;

     for(int i=; i<=n; i++)

     {

         while(l<=r&&moni[l]<i-m+)

             l++;

         while(l<=r&&sto[i]>sto[moni[r]]){

             r--;

         }

              moni[++r]=i;

         if(i>=m)

             maxx[++tot]=moni[l];

     }

     for(int i=; i<=tot; i++)

     {

         if(i==)

             printf("%d",sto[minn[i]]);

         else

             printf(" %d",sto[minn[i]]);

     }

     printf("\n");

     for(int i=; i<=tot; i++)

     {

         if(i==)

             printf("%d",sto[maxx[i]]);

         else

             printf(" %d",sto[maxx[i]]);

     }

     printf("\n");

     return ;

 }

（我太菜了，，，数组模拟调了半个小时。。）