首页 > 其他分享 >单调队列

单调队列

时间:2022-10-23 00:33:21浏览次数:63  
标签:队列 元素 hh int 最小值 单调

单调队列

思想

以寻找滑动窗口中的最小值为例
维护一个最小值的队列,队头为最小值,
将最新的数组元素加入队尾时,
将队列中比最新的数组元素小的元素从尾部出队,
这样我们就维护了一个有关最小值的单调递增队列

代码模板

//常见模型:找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1,q[N];//q为单调队列,存储元素的下标
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}

标签:队列,元素,hh,int,最小值,单调
From: https://www.cnblogs.com/fsh001/p/16817707.html

相关文章

  • 数据结构_用数组实现环形队列
    思路分析:一、front就指向队列的第一个元素,也就是说,arr[front]就是队列的第一个元素 二、rear就是指向队列的最后一个元素的后一个位置,我们需要空出这个rear指向的空间(......
  • 13-13-消息队列设计实践课_ev
                                        ......
  • leetcode(30)单调栈
    6077.巫师的总力量和注意:因为要求连续,所以不能用回溯的方法做496.下一个更大元素I子数组的最小值之和子数组最小乘积的最大值子数组范围和901.股票价格跨度用......
  • 利用redis作为消息队列实现异步秒杀业务
    实现消费券秒杀的优化,在加入限时抢购的优惠券时,自动的将消费券的库存stock信息也加入到redis中(可设为抢购结束后过期)抢购之前在redis中进行库存是否充足(stock)、用户是否已......
  • 刷题 LeetCode 栈和队列2
    代码随想录LeetCode20. 有效的括号carl栈思路左括号入栈,右括号出栈,如果出栈时栈为空或不匹配,或者最终栈不为空则false细节LeetCode1047. 删除字符串中的所有......
  • ModStart: 宝塔配置 MySQL 队列调度
    宝塔配置MySQL队列调度执行以下操作前提前进入网站根目录,如​​cd/www/wwwroot/xxx.com​​执行​​artisan​​ 命令前请参照开发教程→开发使用问题→如何运行​......
  • 消息队列的解释【杭州多测师】【杭州多测师_王sir】
    一、消息队列概述消息队列中间件是分布式系统中重要的组件,主要解决应用解耦,异步消息,流量削锋等问题,实现高性能,高可用,可伸缩和最终一致性架构。目前使用较多的消息队列有A......
  • 单调栈(P1823 [COI2007] Patrik 音乐会的等待)
    [COI2007]Patrik音乐会的等待题目描述\(n\)个人正在排队进入一个音乐会。人们等得很无聊,于是他们开始转来转去,想在队伍里寻找自己的熟人。队列中任意两个人\(a\)和......
  • 单调队列优化dp(1)(P2034 选择数字)
    参考算法学习笔记(66):单调队列-知乎(zhihu.com)题目描述给定一行n个非负整数a[1]..a[n]。现在你可以选择其中若干个数,但不能有超过k个连续的数字被选择。你的任务是......
  • 刷题 LeetCode 栈和队列1
    代码随想录LeetCode232. 用栈实现队列carl栈#队列思路stack和queue的接口和性质细节stack的pop()没有返回值LeetCode225. 用队列实现栈carl栈#队列......