维护一个滑动窗口中的最小值 其右边界增大时 相当于王其中增加元素 左边界增大时 相当于删除元素 窗口整体向右滑动

若窗口中的元素为

2 1

因为窗口整体是向右滑动的 所以2永远不会成为最小值。 将这些元素看成一个队列

因此，每次加入一个元素时都应该从队头删除 他前面的比它大的元素 使整个序列成为递增序列

如 本来队列里是 2 4 6 8 10

加入了 7后要删除 8 10 使此时队列成为 2 4 6 7的递增序列

然后还要从队尾删除不在窗口范围内的元素 。

由于 每个元素最多被删除一次 所以总的时间复杂度是 O(n)

 

poj 2823  Sliding Window

【题意】 一个长度为n的数字序列  ，一个向右的滑动窗口大小为k 求每次 在这个窗口中的 最大值和最小值

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6  7 using namespace std; 8  9 struct node{
   int a, hao;};10 deque 
          
            qzeng,qjian;11 int ans1[1000002],ans2[1000002];12 13 int main()14 {15 node t;16 int i,n,m,num1,num2,x;17 scanf("%d%d",&n,&m);18 19 num1=0;num2=0;20 21 for(i=1;i
           
            =x)26 qzeng.pop_back();27 qzeng.push_back(t);28 29 while(!qjian.empty()&&qjian.back().a<=x)30 qjian.pop_back();31 qjian.push_back(t);32 33 34 }35 for(i=m;i<=n;i++)36 {37 scanf("%d",&x);38 t.a=x; t.hao=i;39 40 41 while(!qzeng.empty()&&qzeng.back().a>=x)42 qzeng.pop_back();43 qzeng.push_back(t);44 45 while(i-qzeng.front().hao>=m)46 qzeng.pop_front();47 ans1[num1++]=qzeng.front().a;48 49 50 51 while(!qjian.empty()&&qjian.back().a<=x)52 qjian.pop_back();53 qjian.push_back(t);54 55 while(i-qjian.front().hao>=m)56 qjian.pop_front();57 ans2[num2++]=qjian.front().a;58 }59 60 for(i=0;i
           
          
         
        
       
      
     

 

 

hdu 3706

【题意】：给三个数 n a b  ，  1 <= n <= 10^7   

              S_i = Aⁱ mod B    , T_i = Min{ S_k | i-A <= k <= i, k >= 1}

           求所有T_i (1 <= i <= n) mod B 的乘积  

【注意】 ： 虽然每个s都会对b取余按理int 不会溢出的  但是这里用int 硬是wa  用__int64 才能过

                还有

 

1 #include 
     
       5 #include 
      
        7 using namespace std; 8  9 __int64 a[1000002],qian[1000002],hou[1000002],i,j,n,m,k; 12 int main()13 {14     while(~scanf("%d",&n))15     {16         if(n==0)17             break;18         for(i=1;i<=n;i++)19            {
    21                scanf("%I64d",&a[i]);22                qian[i]=i;23                hou[i]=i;24            }25            for(i=2;i<=n;i++)26                while(qian[i]>1&&a[qian[i]-1]>=a[i])27                     qian[i]=qian[qian[i]-1];28            for(i=n;i>=1;i--)29                while(hou[i]
       
        =a[i])30                 hou[i]=hou[hou[i]+1];31                 __int64 ans=0;32             for(i=1;i<=n;i++)33             {34                 __int64 temp;35                 temp=(hou[i]-qian[i]+1)*a[i];36                 if(ans