当前位置: 首页 > news >正文

单调队列 (1) - 详解

一,单调队列是什么(介绍)

数据结构

1.单调是数据(目前为线性表)排列的特征 ———  

每下一位的数   都比   这一位   大(或小)

好吧,再说简单一点:递增(或递减)

2.队列是这些特征存在的依托    (结构)队列都知道吧

3.还有:(其余分类)

单调队列不一定是严格递增或递减的

可以为严格单调队列非严格单调队列  (就是有没有数据值相等的情况)

e.g. 

1  2  2  3  3   是非严格单调队列    

1   2   3   4    是严格单调递增队列 

(这些都是根据场景使用的)

二,单调队列的构造

1.单调队列是队列

普通的队列内部的数据值都是不规则的

而单调队列:数据排列递增或递减(这里记作①)

2.从普通队列为空,插入时改变操作,每次插入都要保证①

那就要在新加入数据时,改变不符合的数据

就有两种情况  ——  改变新数据    或   改变原来的数据

(1).不符合就不加新数据(只操作一次)

此处逻辑如下:

//数组模拟q  l r //严格单调递增
//新数据为x
if(x<=q[r]) break;//加不了
else q[++r]=x;

(2).不符合就剔除原来的数据(可能为多次,用while或for+if)

此处逻辑如下:

while(q[r]>=x && l

(注意判断边界)

三,单调队列可以来干什么(基本应用,后续再讲其余)

在化学中,物质的性质决定它的用途

那么,在编程中,一种特殊的数据结构(此处指单调队列)的构造方法(如上)与特征就可以决定它的应用

构造后基本特征:

它能找到一组数据中最大值或最小值

可以抽象为  函数f(s,t)  ——可以找到从位置s到位置t数据中最大值或最小值

并且可以连续性递推性质,即可以由 f(s,t)与值a[t+1]推出f(s,t+1)

(而且操作简便,不怎么耗时间)

总结:(基本应用)

单调队列可以解决 线性表 连续性 递推区间 的最大/小值问题

http://www.hskmm.com/?act=detail&tid=28461

相关文章:

  • 2025 年 密度 / 净化 / 零醛添加 / 装修 / 生态板 / 指接板板材厂家推荐:纯品梅花深耕高端定制,打造健康家居板材优质选择
  • 深入解析:考研复习-线性代数-第二章-矩阵
  • PHP 与 HTML 混写基础
  • 2025 年隧道/车丝/打孔/矿用/R780/钢花钢管厂家推荐榜:精准匹配施工需求,优选可靠供应商
  • 2025 年最新推荐!空压机租赁公司综合实力榜单:涵盖无油 / 高压 / 阿特拉斯等机型及二手买卖置换回收,助力企业精准选靠谱服务商
  • 小波神经网络(WNN)预测代码
  • 2025 年报警器厂家最新推荐权威榜单:海湾 / 青鸟 / 利达等品牌全覆盖,详解优质服务商助力安全选购NB烟感/松江烟感/三江烟感/燃气报警器厂家推荐
  • 优秀的研发经理,如何布局一周的工作?
  • Numerical Heat Transfer and Fluid Flow(《传热与流体流动的数值计算》)
  • 2025天文台圆顶加工厂家最新推荐榜:专业工艺与品质保障之选
  • 2025风机盘管厂家实力推荐:技术领先与品质保障的行业标杆
  • 2025蒸发式冷气机厂家TOP5推荐:节能降温与耐用品质深度
  • 2025 电缆绝缘材料生产厂家最新推荐榜单:技术实力型企业揭晓,选购指南同步发布
  • 基于Java+Springboot+Vue开发的体育场馆预约管理系统源码+运行步骤
  • Linux 终端查看最消耗 CPU 内存的进程
  • 2025 酒店家具厂家最新推荐榜:北木斋领衔五大实力品牌,品质与创新双驱动选购指南智能酒店家具厂家推荐
  • CRM选型指南 | CRM软件成本拆解:本地部署、云租赁
  • 宜倍鲜携手纷享销客CRM开启数字化转型(附四大核心场景)
  • IDEA创建maven项目的不同模板的含义
  • 示波器BLDC需要知道的知识
  • 直播app源码,如何提升用户登录验证的安全性? - 云豹科技
  • 2025 年国内包装袋厂家最新推荐排行榜:聚焦绿色环保与定制化,精选优质企业助力采购决策无纺布/降解/塑料/复合/可定制化包装袋厂家推荐
  • Redis Stack搭建
  • CISA与USCG在关键基础设施威胁狩猎中发现网络安全改进领域
  • 2025年智慧物联与电子信息工程国际学术会议(IoTEIE 2025)
  • 重磅更新:Claude Code 现在支持插件啦!!
  • 标签的关系,注释,标题标签和段落标签,文本格式化标签
  • 笔记本使用摄像头显示“你的相机报告设备上的开关或按钮已阻止或关闭它”(特别是联想笔记本)
  • 牛客刷题-Day11
  • 网络编程实践笔记_1_阿贝云_免费云服务器_简单GET_POST实现