这道题最容易想到的是用朴素的做法，即 每滑动一次，就遍历一次窗口找出最大最小值，这样时间复杂度为O(n*k),由于题目数据比较大，这种做法肯定是超时的。
另外，根据书上的讲解，还可以采用优先队列来求解。用优先队列存储元素下标，根据元素下标找到元素值并进行排序作为优先队列的排序规则。
优先队列的队列首一定是在特定排序规则下的第一个元素。假设优先队列中的元素是大值优先。先用未进行滑动的窗口内元素对优先队列初始化。每向右滑动一次，就需要添加当前元素和删除过期元素。我们需要把当前元素添加到队列中，并且把是当前最大值的过期元素删除，这一步需要循环进行以找出在窗口范围内的当前最大值。如果过期元素不是最大值就不需要删除了，因为反正存在他不会对当前的最大值产生什么影响。
1 #include <cstdio> 2 #include <queue> 3 #include <vector> 4 #include <iterator> 5 using namespace std; 6 vector<int> 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<int>::iterator it = v.begin(); 27 advance(it,k); 28 priority_queue<int,vector<int>,cmp> qmax(cmp(true)); 29 priority_queue<int,vector<int>,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(" "); 53 for(int i = 0; i < cnt; i++){ 54 printf("%d ",dmin[i]); 55 } 56 printf(" "); 57 return 0; 58 }
这种做法时间复杂度为O((n-k)logk)。然而提交之后还是超时。因此只能寻求更高效的解决方法——单调队列。
单调队列中的元素是严格单调的。我们在求解这个问题的时候需要维护他的单调性。队首元素即为当前位置的最大值。
假设要求滑动窗口中的最大值。我们就需要确保滑动窗口中的元素从队首到队尾是递减的。每滑动一次就判断当前元素和队尾元素的关系，如果放入队尾满足单调递减，那么放入即可；如果放入不满足，就需要删除队尾元素直到放入当前元素之后满足队列单调递减。同时要确保已经出窗口的最大值（队首元素）被删除掉。
1 #include <cstdio> 2 #include <deque> 3 #include <vector> 4 using namespace std; 5 const int maxn = 1000000 + 10; 6 vector<int> 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<int> qmax; 18 deque<int> 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 ", dmin[n-1]); 36 for(int i = k-1; i < n-1; i++) 37 printf("%d ", dmax[i]); 38 printf("%d ", dmax[n-1]); 39 return 0; 40 }