生活随笔
收集整理的這篇文章主要介紹了
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（单调队列）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
