2022GDUT寒训专题一I题
admin
撰写于 2022年 01月 22 日

题目

题面

给一个长度为 N的数组,一个长为 K的滑动窗体从最左端移至最右端,你只能看到窗口中的 K 个数,每次窗体向右移动一位,如下图:

窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7

你的任务是找出窗体在各个位置时的最大值和最小值。

输入格式

第 1 行:两个整数 N 和 K; 第 2 行:N个整数,表示数组的 N个元素(≤2e9);

输出格式

第一行为滑动窗口从左向右移动到每个位置时的最小值,每个数之间用一个空格分开; 第二行为滑动窗口从左向右移动到每个位置时的最大值,每个数之间用一个空格分开。

样例

Input&Output

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

思路

这题是滑动窗口找最值问题,我们需要用到的工具是双头的单调队列。

若找的是最大值,则要构造一个递减的队列,反之递增。

解释如下:

1、首先明确我们遍历数组时,当前下标的意思为滑动窗口的右端点为该元素。记滑动窗口大小为k。

2、假设存在滑动窗口右端点a,记滑动窗口下一个元素为b,对于ab二者我们有两种情况:b>=a或者b

3、b>=a:我们知道b在a的右边,那么b影响的范围是[b,b+k-1],a影响的范围是[a,a+k-1]。因为b-a=1,所以b影响的范围始终比a影响的范围大。这意味着,一旦我们能走到b点,a就不再是最大值了,此时a已经没有了任何作用,a从队首出队。在a之前还有a-1,a-2......他们能影响的范围比a还要小,更不可能成为最大值,所以同理他们也从队首出队。一直到队列为空,现在b为新的最大值,为队首。

4、b

5、还需要注意的一点是,滑动窗口是有大小的,所以我们队列中的元素是有“生命周期”的,也就是当前下标-队列元素下标+1要小于等于k

所以我们实际上队列存的是下标,这样引用起来比较方便。

代码

 1 #include 
2 #include
3 using namespace std;
4 //这题是滑动窗口找最大或最小值的问题
5 //要运用到双头单调队列,一直维护最大或最小值,并且由于是滑动窗口所以元素存在生命周期,这里用数组q模拟
6 //
7 int num[1000010];
8 int q[4000020];
9 int main()
10 {
11 ios_base::sync_with_stdio(false);
12 cin.tie(NULL);cout.tie(NULL);
13 //
14 int n, k;cin >> n >> k;
15 for(int i = 0;i < n;++i) cin >> num[i];
16 //
17 int head, tail;
18 //最小值
19 head = 0, tail = 0;
20 //先让第一个元素入队
21 q[head] = 0;
22 for(int i = 0;i < n;++i)
23 {
24 //如果队首元素达到了生命周期,那么队首元素出队直到头尾指针相遇
25 while(head <= tail && i-q[head]+1 > k) head++;
26 if(num[q[head]] >= num[i])
27 {
28 //如果说你比这个队首元素还要小,那么一直出队
29 while(head <= tail && num[q[head]] >= num[i]) head++;
30 //走多了一格,要回去一格
31 q[--head] = i;
32 }else
33 {
34 //否则从队尾入队,但要维护单调性
35 while(head < tail && num[q[tail]] >= num[i]) tail--;
36 q[++tail] = i;
37 }
38 //当且仅当你达到所求滑动窗口大小的时候才能输出
39 if(i >= k-1) printf("%d ", num[q[head]]);
40 }
41 printf("\n");
42 //最大值
43 head = 0, tail = 0;
44 q[head] = 0;
45 for(int i = 0;i < n;++i)
46 {
47 while(head <= tail && i-q[head]+1 > k) head++;
48 if(num[q[head]] <= num[i])
49 {
50 while(head <= tail && num[q[head]] <= num[i]) head++;
51 q[--head] = i;
52 }else
53 {
54 while(head < tail && num[q[tail]] <= num[i]) tail--;
55 q[++tail] = i;
56 }
57 if(i >= k-1) printf("%d ", num[q[head]]);
58 }
59 printf("\n");
60 return 0;
61 }
62 //

2022GDUT寒训专题一I题的

2022GDUT寒训专题一I题

题目

题面

给一个长度为 N的数组,一个长为 K的滑动窗体从最左端移至最右端,你只能看到窗口中的 K 个数,每次窗体向右移动一位,如下图:

窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7

你的任务是找出窗体在各个位置时的最大值和最小值。

输入格式

第 1 行:两个整数 N 和 K; 第 2 行:N个整数,表示数组的 N个元素(≤2e9);

输出格式

第一行为滑动窗口从左向右移动到每个位置时的最小值,每个数之间用一个空格分开; 第二行为滑动窗口从左向右移动到每个位置时的最大值,每个数之间用一个空格分开。

样例

Input&Output

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

思路

这题是滑动窗口找最值问题,我们需要用到的工具是双头的单调队列。

若找的是最大值,则要构造一个递减的队列,反之递增。

解释如下:

1、首先明确我们遍历数组时,当前下标的意思为滑动窗口的右端点为该元素。记滑动窗口大小为k。

2、假设存在滑动窗口右端点a,记滑动窗口下一个元素为b,对于ab二者我们有两种情况:b>=a或者b

3、b>=a:我们知道b在a的右边,那么b影响的范围是[b,b+k-1],a影响的范围是[a,a+k-1]。因为b-a=1,所以b影响的范围始终比a影响的范围大。这意味着,一旦我们能走到b点,a就不再是最大值了,此时a已经没有了任何作用,a从队首出队。在a之前还有a-1,a-2......他们能影响的范围比a还要小,更不可能成为最大值,所以同理他们也从队首出队。一直到队列为空,现在b为新的最大值,为队首。

4、b

5、还需要注意的一点是,滑动窗口是有大小的,所以我们队列中的元素是有“生命周期”的,也就是当前下标-队列元素下标+1要小于等于k

所以我们实际上队列存的是下标,这样引用起来比较方便。

代码

 1 #include 
2 #include
3 using namespace std;
4 //这题是滑动窗口找最大或最小值的问题
5 //要运用到双头单调队列,一直维护最大或最小值,并且由于是滑动窗口所以元素存在生命周期,这里用数组q模拟
6 //
7 int num[1000010];
8 int q[4000020];
9 int main()
10 {
11 ios_base::sync_with_stdio(false);
12 cin.tie(NULL);cout.tie(NULL);
13 //
14 int n, k;cin >> n >> k;
15 for(int i = 0;i < n;++i) cin >> num[i];
16 //
17 int head, tail;
18 //最小值
19 head = 0, tail = 0;
20 //先让第一个元素入队
21 q[head] = 0;
22 for(int i = 0;i < n;++i)
23 {
24 //如果队首元素达到了生命周期,那么队首元素出队直到头尾指针相遇
25 while(head <= tail && i-q[head]+1 > k) head++;
26 if(num[q[head]] >= num[i])
27 {
28 //如果说你比这个队首元素还要小,那么一直出队
29 while(head <= tail && num[q[head]] >= num[i]) head++;
30 //走多了一格,要回去一格
31 q[--head] = i;
32 }else
33 {
34 //否则从队尾入队,但要维护单调性
35 while(head < tail && num[q[tail]] >= num[i]) tail--;
36 q[++tail] = i;
37 }
38 //当且仅当你达到所求滑动窗口大小的时候才能输出
39 if(i >= k-1) printf("%d ", num[q[head]]);
40 }
41 printf("\n");
42 //最大值
43 head = 0, tail = 0;
44 q[head] = 0;
45 for(int i = 0;i < n;++i)
46 {
47 while(head <= tail && i-q[head]+1 > k) head++;
48 if(num[q[head]] <= num[i])
49 {
50 while(head <= tail && num[q[head]] <= num[i]) head++;
51 q[--head] = i;
52 }else
53 {
54 while(head < tail && num[q[tail]] <= num[i]) tail--;
55 q[++tail] = i;
56 }
57 if(i >= k-1) printf("%d ", num[q[head]]);
58 }
59 printf("\n");
60 return 0;
61 }
62 //

2022GDUT寒训专题一I题的

赞 (0)

猜您想看

评论区(暂无评论)

这里空空如也,快来评论吧~

我要评论