【单调队列】 单调队列的“扫描线”理解

这篇具有很好参考价值的文章主要介绍了【单调队列】 单调队列的“扫描线”理解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【单调队列】 单调队列的“扫描线”理解

  “如果一个选手比你小还比你强,你就可以退役了。”——单调队列的原理

  • 比你强,而且比你影响时间更长。
  • 某种意义上,数学思维是生活中的思考的延伸。

  算法学习笔记(66): 单调队列。引用 Pecco 的算法笔记。

  在这里给出一种扫描线的理解。

【单调队列】 单调队列的“扫描线”理解

  我们以滑动窗口长度为 5,维护区间最大值为例子。

  图中横轴表示数组元素位置,纵轴表示数组元素大小,线表示每个数字的影响范围,对应记录的是长度为 k 的滑动窗口区间起点。因此,线段的右端点就是数组元素本身的位置。滑动窗口在图中仅仅需要标出起点的位置(一根竖线),就可以知道有哪些数字了。

  我们考虑后前后两段线。假如后一段大于等于前一段,那么后一段的影响未来范围比前一段更长,就可以在未来一直压着前一段。于是前一段没用了,弹出。(也就是说你预先考虑了一下未来的情况,然后弹出了)假如后一段小于前一段,虽然在过去和未来有限的时间里,前一段会压着后一段,但是后一段仍有不被压着的时候,因此后一段需要保留。

  当我们再直接观察队列中的弹出操作时候,就可以理解,弹出是因为之前的数影响范围被当前的更大的数字覆盖掉了。前面不弹出的是因为还有影响的可能。

  在这个问题中,序列本身是没有方向的,从左向右或者从右向左都行。我们进行滑动窗口的时候,需要规定一个方向。这个方向是无所谓的,但是一旦有了方向,这其中包含的已知到未知推导过程中前后顺序的维护信息,导致了单调队列的“覆盖”与弹出。剩下的“可能有贡献”的元素需要留着。删除不可能的,保留可能的,最后在某一时刻,从所有可能的中,选出确定的。

  为什么单调队列是单调的?我们考虑开始的时候用一个普通队列来维护,前后顺序是元素在序列中的顺序。每加入一个元素的时候,找一遍队列中的小于它的元素,删掉,再加入末尾(因为队列前后顺序和序列前后顺序是一样的)。这时候,查找就找这个队列里面的最大值。弹出照常。这两个操作现在还都是 \(O(k)\) 的。\(k\) 是滑动窗口长度。

  现在我们归纳地证一下。一个元素是有序的;对于新来的元素,改变一下操作顺序,先插入这个序列的正确排序的位置,再删除。有序序列删掉一些数还有序。于是 \(n\) 可以推 \(n+1\)。于是就都成立了。然后就有 \(O(1)\) 的取最大值和总和 \(O(n)\) 的插入删除操作了。\(n\) 是序列长度。文章来源地址https://www.toymoban.com/news/detail-650533.html

到了这里,关于【单调队列】 单调队列的“扫描线”理解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【计算机图形学 】扫描线多边形填充算法 | OpenGL+鼠标交互

    传送门 实现多边形扫描线填充算法,并和鼠标进行交互。 具体原理略过,会贴上完整代码,可直接运行。 环境: vs2019,OpenGL的库(可以搜索如何用vs使用OpenGL的库,可以使用vs自带的插件或者其他方法,很方便) 要点: 1.NET和AET的创建,改动 2.改变鼠标点击和鼠标拖拽的响应

    2023年04月08日
    浏览(78)
  • 计算机图形学实验——利用MFC对话框实现多边形绘制与填充(扫描线填充算法)附源码

    内容概括: 利用基于对话框的MFC项目 实现鼠标点击绘制多边形 实现扫描线算法填充多边形 源码见Yushan-Ji/ComputerGraphics: ECNU2023秋 计算机图形学课程实验代码 (github.com) 通过鼠标交互输入多边形 对各种多边形进行填充,包括边界自交的情况 利用 OnLButtonDown 和 OnRButtonDown 函数,

    2024年02月04日
    浏览(76)
  • C++ 单调队列 || 单调队列模版题:滑动窗口

    给定一个大小为 n≤106 的数组。 有一个大小为 k 的滑动窗口,它从数组的最左边移动到最右边。 你只能在窗口中看到 k 个数字。 每次滑动窗口向右移动一个位置。 以下是一个例子: 该数组为 [1 3 -1 -3 5 3 6 7],k 为 3 。 窗口位置 最小值 最大值 [1 3 -1] -3 5 3 6 7 -1 3 1 [3 -1 -3] 5

    2024年01月20日
    浏览(41)
  • 单调队列&单调栈

    在一些问题中,可以使用单调队列或者单调栈优化 时间复杂度一般会被优化为 (O(n)) 单调队列: 队尾可以进队出队,对头可以出队(维护队列的单调性,往往会配合二分进一步降低时间复杂度) 队尾出队 的条件是:队列不空且新元素更优,队中的旧元素队尾出队 每个元素

    2024年02月05日
    浏览(36)
  • 【学习笔记】单调队列和单调栈

    以这道题为例:P5788。我们考虑维护一个单调栈,里面存的是下标,使里面的下标对应的元素从栈顶到栈底是单调上升的。 我们从 (nrightarrow 1) 枚举 (a_i) 对于每个 (i) ,如果栈非空,令栈顶的下标为 (j) ,若 (a_j) 不比 (a_i) 大,那么这个栈顶元素由于值又小,位置又靠

    2024年02月15日
    浏览(38)
  • 算法模板之单调栈和单调队列图文详解

    🌈个人主页: 聆风吟 🔥系列专栏: 算法模板、数据结构 🔖少年有梦不应止于心动,更要付诸行动。      💬 hello! 各位铁子们大家好哇,今天作者给大家带来了单调栈和单调队列的算法模板讲解,让我们一起加油进步。      📚 系列专栏:本期文章收录在《算法

    2024年02月02日
    浏览(46)
  • 蓝桥杯每日一题----单调栈和单调队列

    单调栈即栈内的元素是单调递减或者单调递增的,我们通过一个题目来理解。 单调栈模板题 题目描述 给出项数为 n 的整数数列 a 1 … a n a_1…a_n a 1 ​ … a n ​ 。 定义函数 f ( i ) f(i) f ( i ) 代表数列中第 i 个元素之后第一个大于 a i a_i a i ​ 的元素的下标,即 f ( i ) = m i n i

    2024年02月19日
    浏览(42)
  • 辅助栈、单调栈与单调队列在lc中的应用

    三者都有何区别? 个人建议 单调栈/队列 中存放的元素最好是下标而不是值,因为有的题目需要根据下标计算,这样泛化性更好。参考lc239和lc496 大概的思路是先把不满足单调性的元素poll掉,然后offer一个当前符合条件的元素。参考lc239和lc496 // 说明:这里使用两个堆来维护

    2024年02月14日
    浏览(37)
  • leetcode分类刷题:队列(Queue)(一、单调队列)

    单调队列,看起来是与单调栈对应起来的一样;但是做题的时候感觉单调队列不像单调栈一样,能根据题意自然形成 单调队列的基本实现 ,感觉单调队列更像是和某个队列对应起来的一样 1、 单调队列的经典题型 :使用双向队列维护窗口,窗口移动的元素增删与队列的先进

    2024年02月09日
    浏览(41)
  • 算法设计-单调队列

    这个东西我弄得还不是很明白,所以先放一篇博客:https://www.cnblogs.com/I-Love-You-520/p/13454305.html ​ 单调队列说的就是博客中提到的场景,可以说解决的是 固定长度,多次查询一段的最值 (其实就是slice window的意思),这种如果是朴素算法的话,因为查一段序列的最值的时间复

    2023年04月08日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包