单调队列
发布日期:2021-08-14 10:59:13 浏览次数:1 分类:技术文章

本文共 1545 字,大约阅读时间需要 5 分钟。

单调队列

性质

单调队列和单调栈很像,就是一个维护了单调性的队列数据结构,可以是单调递增的,也可以是单调递减的。

模型

下图是一个单调递增的单调队列模型。

其中元素也是从小到大排列。

和单调栈的操作一样,如果加入一个满足单调性的元素,例如5,那么就直接加入。

 

那么如果加入一个元素3呢?我们维护单调性,需要把队列尾端把大于3的元素全部弹出,那么就需要用双端队列来实现了,当然操作和单调栈是一样的。

 

单调队列有许多作用:

比如可以求出一个数组内第一个大于等于一个数x的数

也可以通过维护单调性,解决一些区间内最小或最大的问题

总之单调队列的应用在根本上要视题目而定的灵活运用

本质上并不复杂

 

 

题目描述

现在有一堆数字共N个数字(N<=10^6),以及一个大小为k

的窗口。现在这个从左边开始向右滑动,每次滑动一个单

位,求出每次滑动后窗口中的最大值和最小值。

例如:

The array is [1 3 -1 -3 5 3 6 7], and k = 3.

输入格式:

输入一共有两行,第一行为n,k。

第二行为n个数(<INT_MAX).

输出格式:

输出共两行,第一行为每次窗口滑动的最小值

第二行为每次窗口滑动的最大值

输入输出样例

输入样例#1:

8 3

1 3 -1 -3 5 3 6 7

输出样例#1:

-1 -3 -3 -3 3 3

3 3 5 5 6 7

 

请用C++提交

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f#define LL long long#define MAXN 2000005using namespace std;struct Node{ int index; int val;};int a[MAXN];deque
q;int main(){ int n,m; Node node; scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=1;i<=n;i++) // 区间最大值 { node.val = a[i]; node.index = i; while (!q.empty() && q.back().val
=m) { while (!q.empty() && q.front().index+m<=i) q.pop_front(); printf("%d\n",q.front().val); } } while (!q.empty()) //区间最小值 q.pop_front(); for (int i=1;i<=n;i++) { node.val = a[i]; node.index = i; while (!q.empty() && a[i]
=m) { if (!q.empty() && q.front().index+m<=i) q.pop_front(); printf("%d\n",q.front().val); } } return 0;}

 

转载于:https://www.cnblogs.com/-Ackerman/p/11276929.html

转载地址:https://blog.csdn.net/weixin_30719711/article/details/98296616 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Dijkstra's Minimum Distance
下一篇:spring

发表评论

最新留言

路过,博主的博客真漂亮。。
[***.116.15.85]2024年03月12日 09时55分21秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

java buffer nio_Java NIO之Buffer(缓冲区)入门 2019-04-21
android java加密_android 和java平台通用的AES加密解密 2019-04-21
java导出类_java导出excel工具类 2019-04-21
java学习手册下载_Java学习手册 2019-04-21
axios delete有请求体吗_关于axios请求——delete方法 2019-04-21
java 自助更改密码 api_搭建ldap自助修改密码系统--Self Service Password 2019-04-21
php继承exten,stylus中文文档 » 继承(@extend) » 张鑫旭-鑫空间-鑫生活 2019-04-21
mysql函数大全 pdf,MySQL函数大全 2019-04-21
php 常用文件系统函数,php 文件系统函数整理介绍 2019-04-21
android pm.java,java – AM / PM的Android DateFormat因设备而异 2019-04-21
oracle存储过程调用sql文件,oracle - 在SQL Developer中运行存储过程? 2019-04-21
oracle同时报604和12507,V$SES_OPTIMIZER_ENV 查不到刚修改的隐含参数, 2019-04-21
zblog的php更换域名,zblogphp更换域名后,原zblog里使用了固定域名,登录不进去怎么办... 2019-04-21
oracle dnfs 配置,Source of Oracle参数解析(dnfs_batch_size) - django-\/\/ i K | 2019-04-21
oracle所需的环境,转:面对一个全新的oracle环境,首先应该了解什么? 2019-04-21
linux 小数四则运行,shell四则运算(整数及浮点数)的方法介绍 2019-04-21
linux系统分区后进入紧急模式,Linux系统的救援模式应用详解 2019-04-21
linux配置匿名ftp服务器,在Linux环境中使用vsftpd搭建ftp实现匿名上传详细配置 2019-04-21
linux创建硬盘分区lvm,LVM创建及分区调整、更换LVM硬盘 2019-04-21
FreeBSD可以安装Linux软件吗,在Linux服务器上面通过网络安装FreeBSD 2019-04-21