生活随笔
收集整理的这篇文章主要介绍了
POJ 2823 Sliding Window（单调队列）
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
http://poj.org/problem?id=2823
题意：
给出数组和滑动窗口的大小，每次输出滑动窗口中的最大值和最小值。
思路：
这题可以算是单调队列的模板题了，分别维护单调递增和单调递减的队列，队尾在每次插入时维护即可，队首的维护是当队首元素不在滑动窗口范围内时就舍去。
1 #include<iostream>
2 #include<algorithm>
3 #include<cstring>
4 #include<cstdio>
5 #include<vector>
6 #include<stack>
7 #include<queue>
8 #include<cmath>
9 #include<map>
10 #include<
set>
11 using namespace std;
12 typedef
long long ll;
13 typedef pair<
int,
int>
pll;
14 const int INF =
0x3f3f3f3f;
15 const int maxn = 1e6+
5;
16
17 int n, k;
18 int a[maxn];
19 int q[maxn];
20 int p[maxn];
21
22 void get_min()
23 {
24 int frt=
1,rear=
1;
25 for(
int i=
1;i<k;i++
)
26 {
27 while(frt<=rear && q[rear]>=a[i]) rear--
;
28 q[++rear]=
a[i];
29 p[rear]=
i;
30 }
31 for(
int i=k;i<=n;i++
)
32 {
33 while(frt<=rear && q[rear]>=a[i]) rear--
;
34 q[++rear]=
a[i];
35 p[rear]=
i;
36 while(p[frt]<i-k+
1) frt++
;
37 printf(
"%d%c",q[frt],i==n?
'\n':
' ');
38 }
39 }
40
41 void get_max()
42 {
43 int frt=
1,rear=
1;
44 for(
int i=
1;i<k;i++
)
45 {
46 while(frt<=rear && q[rear]<=a[i]) rear--
;
47 q[++rear]=
a[i];
48 p[rear]=
i;
49 }
50 for(
int i=k;i<=n;i++
)
51 {
52 while(frt<=rear && q[rear]<=a[i]) rear--
;
53 q[++rear]=
a[i];
54 p[rear]=
i;
55 while(p[frt]<i-k+
1) frt++
;
56 printf(
"%d%c",q[frt],i==n?
'\n':
' ');
57 }
58 }
59
60 int main()
61 {
62 //freopen("in.txt","r",stdin);
63 while(~scanf(
"%d%d",&n,&
k))
64 {
65 for(
int i=
1;i<=n;i++) scanf(
"%d",&
a[i]);
66 get_min();
67 get_max();
68 }
69 return 0;
70 }
转载于:https://www.cnblogs.com/zyb993963526/p/7624413.html
总结
以上是生活随笔为你收集整理的POJ 2823 Sliding Window（单调队列）的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
