POJ 2823 Sliding Window（单调队列）

怼烎@ 2022-06-11 23:48 161阅读 0赞

An array of size *n* ≤ 10 6 is given to you. There is a sliding window of size *k*which is moving from the very left of the array to the very right. You can only see the *k* numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:  
The array is \[1 3 -1 -3 5 3 6 7\], and *k* is 3.

<table> 
 <tbody> 
 <tr> 
 <th>Window position</th> 
 <th>Minimum value</th> 
 <th>Maximum value</th> 
 </tr> 
 <tr> 
 <td>[1&nbsp;&nbsp;3&nbsp;&nbsp;-1]&nbsp;-3&nbsp;&nbsp;5&nbsp;&nbsp;3&nbsp;&nbsp;6&nbsp;&nbsp;7&nbsp;</td> 
 <td align="RIGHT">-1</td> 
 <td align="RIGHT">3</td> 
 </tr> 
 <tr> 
 <td>&nbsp;1&nbsp;[3&nbsp;&nbsp;-1&nbsp;&nbsp;-3]&nbsp;5&nbsp;&nbsp;3&nbsp;&nbsp;6&nbsp;&nbsp;7&nbsp;</td> 
 <td align="RIGHT">-3</td> 
 <td align="RIGHT">3</td> 
 </tr> 
 <tr> 
 <td>&nbsp;1&nbsp;&nbsp;3&nbsp;[-1&nbsp;&nbsp;-3&nbsp;&nbsp;5]&nbsp;3&nbsp;&nbsp;6&nbsp;&nbsp;7&nbsp;</td> 
 <td align="RIGHT">-3</td> 
 <td align="RIGHT">5</td> 
 </tr> 
 <tr> 
 <td>&nbsp;1&nbsp;&nbsp;3&nbsp;&nbsp;-1&nbsp;[-3&nbsp;&nbsp;5&nbsp;&nbsp;3]&nbsp;6&nbsp;&nbsp;7&nbsp;</td> 
 <td align="RIGHT">-3</td> 
 <td align="RIGHT">5</td> 
 </tr> 
 <tr> 
 <td>&nbsp;1&nbsp;&nbsp;3&nbsp;&nbsp;-1&nbsp;&nbsp;-3&nbsp;[5&nbsp;&nbsp;3&nbsp;&nbsp;6]&nbsp;7&nbsp;</td> 
 <td align="RIGHT">3</td> 
 <td align="RIGHT">6</td> 
 </tr> 
 <tr> 
 <td>&nbsp;1&nbsp;&nbsp;3&nbsp;&nbsp;-1&nbsp;&nbsp;-3&nbsp;&nbsp;5&nbsp;[3&nbsp;&nbsp;6&nbsp;&nbsp;7]</td> 
 <td align="RIGHT">3</td> 
 <td align="RIGHT">7</td> 
 </tr> 
 </tbody> 
</table>

Your task is to determine the maximum and minimum values in the sliding window at each position.

Input

The input consists of two lines. The first line contains two integers *n* and *k* which are the lengths of the array and the sliding window. There are *n* integers in the second line.

Output

There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.

Sample Input

8 3
    1 3 -1 -3 5 3 6 7

Sample Output

-1 -3 -3 -3 3 3
    3 3 5 5 6 7

题解：

我从未见过如此厚颜无耻之题。。。如果你是因为用了单调队列还是tle，那么你就回去把g++改成c++，应该可以ac了。。。我不想吐槽了，我检查了一上午为什么tle，甚至手写双向队列，各种提速，就在我绝望的时候随手改成了c++。。。ac了，才用了6000ms。。一半的时间，我的内心有一万只草尼玛经过

说下思路：

这题可以不用手写双向队列。。用stl的就可以，deque，我是tle了n次改的手写，比如求最大值来说，就是全部扫一遍，首先判断是否头结点已经‘’过期‘’了，即出了限定范围，如果过期了就删掉，拿当前的值和队头做比较，如果比他大直接全清空，加入节点，如果不是，就和队尾比较，如果比队尾大，就把队尾pop，继续循环，最后加入节点。。整个过程使队列保持单调性，同理求最小值也是这样，这样可以在o（n）的范围内解出题

至于单调队列的解释，引用：

解决这个问题可以使用一种叫做单调队列的数据结构，它维护这样一种队列：

a)从队头到队尾，元素在我们所关注的指标下是递减的（严格递减，而不是非递增），比如查询如果每次问的是窗口内的最小值，那么队列中元素从左至右就应该递增，如果每次问的是窗口内的最大值，则应该递减，依此类推。这是为了保证每次查询只需要取队头元素。

b)从队头到队尾，元素对应的时刻（此题中是该元素在数列a中的下标）是递增的，但不要求连续，这是为了保证最左面的元素总是最先过期，且每当有新元素来临的时候一定是插入队尾。

满足以上两点的队列就是单调队列，首先，只有第一个元素的序列一定是单调队列。

那么怎么维护这个单调队列呢？无非是处理插入和查询两个操作。

对于插入，由于性质b，因此来的新元素插入到队列的最后就能维持b)继续成立。但是为了维护a)的成立，即元素在我们关注的指标下递减，从队尾插入新元素的时候可能要删除队尾的一些元素，具体说来就是，找到第一个大于（在所关注指标下）新元素的元素，删除其后所有元素，并将新元素插于其后。因为所有被删除的元素都比新元素要小，而且比新元素要旧，因此在以后的任何查询中都不可能成为答案，所以可以放心删除。

对于查询，由于性质b，因此所有该时刻过期的元素一定都集中在队头，因此利用查询的时机删除队头所有过期的元素，在不含过期元素后，队头得元素就是查询的答案（性质a），将其返回即可。

由于每个元素都进队出队一次，因此摊销复杂度为O(n)。

原博客：http://www.cnblogs.com/Jason-Damon/archive/2012/04/19/2457889.html

代码：

#include<algorithm>
 #include<iostream>
 #include<cstring>
 #include<stdio.h>
 #include<math.h>
 #include<string>
 #include<stdio.h>
 #include<queue>
 #include<stack>
 #include<map>
 using namespace std;
 const int N=1e6+5;
 struct node
 {
 int b;
 int v;
 };
 struct que//我自己手写的双向队列..被判断系统整的无语了
 {
 node q[N];
 int head,tail;
 que()
 {
 head=0;
 tail=0;
 }
 int empty()
 {
 if(head==tail)
 return 1;
 return 0;
 }
 void push_back(const node& x)
 {
 q[tail]=x;
 tail++;
 }
 node& front()
 {
 return q[head];
 }
 node& back()
 {
 return q[tail-1];
 }
 void pop_back()
 {
 tail--;
 }
 void pop_front()
 {
 head++;
 }
 void clear()
 {
 tail=head;
 }
 };
 que q1;
 que q2;
 int minn[N];//保存最大最小值
 int maxx[N];
 int main()
 {
 int i,j,k,n,w,x;
 node now1,now2,now;
 scanf("%d%d",&n,&w);
 scanf("%d",&x);
 if(n==1)
 {
 printf("%d\n%d\n",x,x);
 return 0;
 }
 if(w==1)//为了省时间一开始就输出特判一下
 {
 printf("%d ",x);
 }
 minn[0]=x;
 maxx[0]=x;
 now1.b=0;
 now1.v=x;
 q1.push_back(now1);
 q2.push_back(now1);
 for(i=1;i<n;i++)
 {
 now1=q1.front();
 now2=q2.front();
 while(now1.b+w-1<i)//检查过期
 {
 q1.pop_front();
 if(q1.empty())
 break;
 now1=q1.front();
 }
 while(now2.b+w-1<i)
 {
 q2.pop_front();
 if(q2.empty())
 break;
 now2=q2.front();
 }
 scanf("%d",&x);
 now.b=i;
 now.v=x;
 if(!q1.empty()&&q1.front().v<=x)//检查队头
 q1.clear();
 else
 while(!q1.empty()&&q1.back().v<=x)//检查队尾
 q1.pop_back();
 q1.push_back(now);
 maxx[i]=q1.front().v;
 if(!q2.empty()&&q2.front().v>=x)
 q2.clear();
 else
 while(!q2.empty()&&q2.back().v>=x)
 q2.pop_back();
 q2.push_back(now);//放进去
 minn[i]=q2.front().v;
 if(i>=w-1)//输出最小值。。可以之后输出的，我为了省时间就在这里输出了。。被tle折磨的
 {
 printf("%d",minn[i]);
 if(i==n-1)
 printf("\n");
 else
 printf(" ");
 }
 }
 for(i=w-1;i<n;i++)
 {
 printf("%d",maxx[i]);
 if(i==n-1)
 printf("\n");
 else
 printf(" ");
 }
 return 0;
 }