1. 首页
  2. 代码宅, 单调队列

【Sliding Windows】

题目描述

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

 

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

输入格式

输入的第 1 行是两个整数 n,k,第 2 行为长度为 n 的数组(即有 n 个整数)。

输出格式

 输出 2 行,第 1 行是每个位置的最小值,第 2 行是每个位置的最大值。

样例数据 1

输入

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

输出

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

备注

【数据范围】
对于 20% 的数据:n<=500;
对于 50% 的数据:n<=100000;
对于 100% 的数据:n<=1000000;、

维护个单调队列就行了,注意(l,r)到(l+1,r+1) 其中(l+1,r)这段区间是公共的,也就是说维护一个单调递减队列,检查一遍最大值如果落在a[l]上就删除队首元素,然后看队尾比a[l+k-1]小的都删掉,因为l+k-1序号比前面打,值也比前面大,相当于前面的都没用了。于是乎单调队列就构造出来了,问题是为啥printf会 TLE啊!!!!!改成cout才AC。

下面是代码:

 

评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
上一篇:
:下一篇

发表评论

gravatar

*

沙发空缺中,还不快抢~