洛谷 P1886 滑动窗口 /【模板】单调队列
发布日期:2021-07-01 02:50:30
浏览次数:4
分类:技术文章
本文共 1592 字,大约阅读时间需要 5 分钟。
题目描述
有一个长为 n n n 的序列 a a a ,以及一个大小为 k k k 的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。 例如:The array is [1,3,-1,-3,5,3,6,7], and k=3
。 输入格式
输入一共有两行,第一行有两个正整数 n , k n,k n,k 。 第二行 n n n 个整数,表示序列 a a a 。输出格式
输出共两行,第一行为每次窗口滑动的最小值,第二行为每次窗口滑动的最大值。输入输出样例
输入 #18 31 3 -1 -3 5 3 6 7
输出 #1
-1 -3 -3 -3 3 33 3 5 5 6 7
说明/提示 【数据范围】
对于 50 % 50\% 50% 的数据, 1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1≤n≤105 ; 对于 100 % 100\% 100% 的数据, 1 ≤ k ≤ n ≤ 1 0 6 , a i ∈ [ − 2 31 , 2 31 ) 1\le k \le n \le 10^6, a_i \in [-2^{31},2^{31}) 1≤k≤n≤106,ai∈[−231,231) 。题意:求出移动的、固定长度的滑动窗口中的最大值序列和最小值序列。
思路:完全套用单调队列的模板,写一个单调递增队列和一个单调递减队列即可,注意:数据数组和队列数组都从 1
开始。代码如下:
#includeusing namespace std;const int maxn = 1e6 + 10;int arr[maxn];int qinc[maxn], finc = 1, rinc = 0;int qdec[maxn], fdec = 1, rdec = 0;int posinc[maxn], posdec[maxn];int minArr[maxn], mincnt = 0;int maxArr[maxn], maxcnt = 0;int main() { int n, k; scanf("%d%d", &n, &k); //从1开始 for (int i = 1; i <= n; ++i) scanf("%d", &arr[i]); for (int i = 1; i <= n; ++i) { //单调递增队列非空时 while (finc <= rinc && arr[i] > qinc[rinc]) --rinc; qinc[++rinc] = arr[i]; posinc[rinc] = i; if (posinc[finc] + k <= i) ++finc; //队首元素超出区间, 出队 if (i >= k) maxArr[maxcnt++] = qinc[finc]; //单调递减队列非空时 while (fdec <= rdec && arr[i] < qdec[rdec]) --rdec; qdec[++rdec] = arr[i]; posdec[rdec] = i; if (posdec[fdec] + k <= i) ++fdec; //队首元素超出区间, 出队 if (i >= k) minArr[mincnt++] = qdec[fdec]; } for (int i = 0; i < mincnt; ++i) printf(" %d" + (!i), minArr[i]); printf("\n"); for (int i = 0; i < maxcnt; ++i) printf(" %d" + (!i), maxArr[i]); return 0;}
提交AC:
转载地址:https://memcpy0.blog.csdn.net/article/details/108271651 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年05月06日 21时43分14秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
x265-1.7版本-common/scalinglist.cpp注释
2019-05-02
x265-1.7版本-common/slice.cpp注释
2019-05-02
x265-1.7版本-common/slice.h注释
2019-05-02
x265-1.7版本-encoder/bitcost.h注释
2019-05-02
x265-1.7版本-encoder/dpb.cpp注释
2019-05-02
x265-1.7版本-encoder/dpb.h注释
2019-05-02
x265-1.7版本-encoder/encoder.cpp注释
2019-05-02
x265-1.7版本-encoder/encoder.h注释
2019-05-02
x265-1.7版本-encoder/frameencoder.cpp注释
2019-05-02
x265-1.7版本-encoder/frameencoder.h注释
2019-05-02
x265-1.7版本-encoder/motion.cpp注释
2019-05-02
高阶函数
2019-05-02
继承和多态
2019-05-02
获取对象信息
2019-05-02
实例属性和类属性
2019-05-02
使用__slots__
2019-05-02
使用@property
2019-05-02
多重继承
2019-05-02
定制类
2019-05-02
使用枚举类
2019-05-02