POJ 2823 (滑动窗口)

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

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

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

 #include <cstdio>

 #include <queue>

 #include <vector>

 #include <iterator>

 using namespace std;

 vector<int> v;

 struct cmp{

     bool rev;

     cmp(const bool rev=false):rev(rev){}

     bool operator()(int s1, int s2){

         if(rev) return v[s1] < v[s2];

         else return v[s1] > v[s2];

     }

 };

 int main(){

     int n , k;

     int cnt = ;

     int dmax[],dmin[];

     scanf("%d%d", &n, &k);

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

         int d;

         scanf("%d",&d);

         v.push_back(d);

     }

     vector<int>::iterator it = v.begin();

     advance(it,k);

     priority_queue<int,vector<int>,cmp>  qmax(cmp(true));

     priority_queue<int,vector<int>,cmp> qmin;

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

         qmax.push(i);

         qmin.push(i);

     }

     dmax[cnt] = v[qmax.top()];

     dmin[cnt] = v[qmin.top()];

     cnt++;

     for(int i = k; i < n; i++,++cnt){

         qmax.push(i);

         qmin.push(i);

         while(i - qmax.top() >= k){

             qmax.pop();

         }

         dmax[cnt] = v[qmax.top()];

         while(i - qmin.top() >= k){

             qmin.pop();

         }

         dmin[cnt] = v[qmin.top()];

     }

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

         printf("%d  ",dmax[i]);

     }

     printf("\n");

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

         printf("%d  ",dmin[i]);

     }

     printf("\n");

     return ;

 }

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

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

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

 #include <cstdio>

 #include <deque>

 #include <vector>

 using namespace std;

 const int maxn =  + ;

 vector<int> v;

 int dmax[maxn];

 int dmin[maxn];

 int main(){

     int n, k;

     scanf("%d%d", &n, &k);

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

         int d;

         scanf("%d", &d);

         v.push_back(d);

     }

     deque<int> qmax;

     deque<int> qmin;

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

         while(!qmax.empty() && v[i] > v[qmax.back()])

             qmax.pop_back();

         if(!qmax.empty() && i - qmax.front() >= k)

             qmax.pop_front();

         qmax.push_back(i);

         while(!qmin.empty() && v[i] < v[qmin.back()])

             qmin.pop_back();

         if(!qmin.empty() && i - qmin.front() >= k)

             qmin.pop_front();

         qmin.push_back(i);

         dmax[i] = v[qmax.front()];

         dmin[i] = v[qmin.front()];

     }

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

         printf("%d ", dmin[i]);

     printf("%d\n", dmin[n-]);

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

         printf("%d ", dmax[i]);

     printf("%d\n", dmax[n-]);

     return ;

 }

巴特西

POJ 2823 (滑动窗口)

最新文章

热门文章