这道题最容易想到的是用朴素的做法，即 每滑动一次，就遍历一次窗口找出最大最小值，这样时间复杂度为O(n*k),由于题目数据比较大，这种做法肯定是超时的。

另外，根据书上的讲解，还可以采用优先队列来求解。用优先队列存储元素下标，根据元素下标找到元素值并进行排序作为优先队列的排序规则。

优先队列的队列首一定是在特定排序规则下的第一个元素。假设优先队列中的元素是大值优先。先用未进行滑动的窗口内元素对优先队列初始化。每向右滑动一次，就需要添加当前元素和删除过期元素。我们需要把当前元素添加到队列中，并且把是当前最大值的过期元素删除，这一步需要循环进行以找出在窗口范围内的当前最大值。如果过期元素不是最大值就不需要删除了，因为反正存在他不会对当前的最大值产生什么影响。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 vector
         
           v; 7 struct cmp{ 8     bool rev; 9     cmp(const bool rev=false):rev(rev){}10     bool operator()(int s1, int s2){11         if(rev) return v[s1] < v[s2];12         else return v[s1] > v[s2]; 13     }14 };15 int main(){16     int n , k;17     int cnt = 0;18     int dmax[100],dmin[100];19     scanf("%d%d", &n, &k);20 21     for(int i = 0; i < n; i++){22         int d;23         scanf("%d",&d);24         v.push_back(d);25     }26     vector
          
           ::iterator it = v.begin();27 advance(it,k);28 priority_queue
           
            
             ,cmp> qmax(cmp(true));29 priority_queue
             
              
               ,cmp> qmin;30 for(int i = 0; i < k; i++){31 qmax.push(i);32 qmin.push(i);33 }34 dmax[cnt] = v[qmax.top()];35 dmin[cnt] = v[qmin.top()]; 36 cnt++; 37 for(int i = k; i < n; i++,++cnt){38 qmax.push(i);39 qmin.push(i);40 while(i - qmax.top() >= k){41 qmax.pop();42 }43 dmax[cnt] = v[qmax.top()];44 while(i - qmin.top() >= k){45 qmin.pop();46 }47 dmin[cnt] = v[qmin.top()];48 }49 for(int i = 0; i < cnt; i++){50 printf("%d ",dmax[i]);51 }52 printf("\n");53 for(int i = 0; i < cnt; i++){54 printf("%d ",dmin[i]);55 }56 printf("\n"); 57 return 0;58 }
              
             
            
           
          
         
        
       
      
     

 

这种做法时间复杂度为O((n-k)logk)。然而提交之后还是超时。因此只能寻求更高效的解决方法——单调队列。

单调队列中的元素是严格单调的。我们在求解这个问题的时候需要维护他的单调性。队首元素即为当前位置的最大值。

假设要求滑动窗口中的最大值。我们就需要确保滑动窗口中的元素从队首到队尾是递减的。每滑动一次就判断当前元素和队尾元素的关系，如果放入队尾满足单调递减，那么放入即可；如果放入不满足，就需要删除队尾元素直到放入当前元素之后满足队列单调递减。同时要确保已经出窗口的最大值（队首元素）被删除掉。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 const int maxn = 1000000 + 10; 6 vector
        
          v; 7 int dmax[maxn]; 8 int dmin[maxn]; 9 int main(){10     int n, k;11     scanf("%d%d", &n, &k);12     for(int i = 0; i < n; i++){13         int d;14         scanf("%d", &d);15         v.push_back(d);16     }17     deque
         
           qmax;18     deque
          
            qmin;19 for(int i = 0; i < n; i++){20 while(!qmax.empty() && v[i] > v[qmax.back()])21 qmax.pop_back();22 if(!qmax.empty() && i - qmax.front() >= k)23 qmax.pop_front();24 qmax.push_back(i);25 while(!qmin.empty() && v[i] < v[qmin.back()])26 qmin.pop_back();27 if(!qmin.empty() && i - qmin.front() >= k)28 qmin.pop_front();29 qmin.push_back(i);30 dmax[i] = v[qmax.front()];31 dmin[i] = v[qmin.front()];32 }33 for(int i = k-1; i < n-1; i++)34 printf("%d ", dmin[i]);35 printf("%d\n", dmin[n-1]);36 for(int i = k-1; i < n-1; i++)37 printf("%d ", dmax[i]);38 printf("%d\n", dmax[n-1]);39 return 0;40 }