首页 > 编程语言 >单调队列算法模板及应用

单调队列算法模板及应用

时间:2023-05-14 13:32:50浏览次数:52  
标签:窗口 队列 ++ tt 最小值 int hh 模板 单调

文章和代码已经归档至【Github仓库:https://github.com/timerring/algorithms-notes 】或者【AIShareLab】回复 算法笔记 也可获取。

队列算法模板

单调队列算法模板及应用_滑动窗口

// hh 表示队头,tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];
// 对尾的值
q[tt];

// 判断队列是否为空
/*
	if(hh <= tt) not empty
	else empty
*/
if (hh <= tt)
{
}

例题:滑动窗口

单调队列的应用:求滑动窗口中的最大值和最小值

第一步把新元素插入队尾,第二步把滑出去的元素从队首弹出来。

给定一个大小为 单调队列算法模板及应用_最小值_02 的数组。

有一个大小为 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 3 6 7

-3

3

1 3 [-1 -3 5] 3 6 7

-3

5

1 3 -1 [-3 5 3] 6 7

-3

5

1 3 -1 -3 [5 3 6] 7

3

6

1 3 -1 -3 5 [3 6 7]

3

7

你的任务是确定滑动窗口位于每个位置时,窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数 n 和 k,分别代表数组长度和滑动窗口的长度。

第二行有 n 个整数,代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出,从左至右,每个位置滑动窗口中的最小值。

第二行输出,从左至右,每个位置滑动窗口中的最大值。

输入样例:

8 3
1 3 -1 -3 5 3 6 7

输出样例:

-1 -3 -3 -3 3 3
3 3 5 5 6 7

求最小值的过程相当于维护了一个升序的序列,每次队尾插入的值会使原队尾大于它的值一直弹出,最后输出时就会弹出该区间的最小值。

思路:

最小值和最大值分开来做,都做以下四步:

  • 队首是否出窗口;
  • 解决队尾与当前元素a[i]不满足单调性;
  • 将当前元素下标加入队尾;(一定要先3后4,因为有可能输出的正是新加入的那个元素;)
  • 如果满足条件则输出结果;

需要注意的细节:

队列中存的是原数组的下标,取值时要再套一层,a[q[]];

算最大值前注意将hh和tt重置;

此题用cout会超时,只能用printf;

hh从0开始,数组下标也要从0开始。

单调队列算法模板及应用_最小值_03

虽然有两个循环,但是时间复杂度是O(N)的,因为while那里判断条件最多执行常数次,比如新加入一个最小值,哪怕一直弹出到队首,队列长度才k个,k是常数,所以while最多执行k次,合起来就是O(kN),化简就是O(N)。

code
# include <iostream>

using namespace std;

const int N = 1000010;
int a[N], q[N];

int main()
{
    int n,k;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
    
    int hh = 0, tt = -1;
    // i是当前枚举的右端点,k是区间的长度
    // 队列q[]中存的是下标
    // 寻找最小值
    for(int i = 0; i < n; i ++)
    {
        // 判断队头是否应该滑出窗口
        // 因为每次窗口只移动一位,因此这里写if即可,不用写while
        // q[tt](队尾序号)的正常范围在i-k+1到i之间 你可以画图模拟一下,很简单
        if(hh <= tt && i - k + 1 > q[hh]) hh ++;
        // 如果新插入的数比队尾数要小的话,就将该队尾弹出
        // 可能会一直弹出到队首,也可能不会(队首比他还小)
        // 相当于维护了一个升序的序列
        while(hh <= tt && a[q[tt]] >= a[i]) tt --; 
        // 然后将i存入q中的队尾
        q[ ++ tt] = i;
        // 如果i比区间长度大的话,打印q队头的序号的元素值,因为如果i从左向右移动还不足k个,那么就不用输出。只要队列目前没有超过 i - k + 1 > q[hh] 的限制,就一直输出队首的最小值。
        // 注意 i 是从 0 开始的,例如k = 3, 因此向右移动三次就是2,k - 1 = 2
        if(i >= k - 1) printf("%d ", a[q[hh]]);
    }
    puts("");
    
    // 最大值是一个完全对称的写法
    hh = 0, tt = -1;
    for(int i = 0; i < n; i ++)
    {
        if(hh <= tt && i - k + 1 > q[hh]) hh ++;
        // 这里把大于改成小于即可
        // 相当于维护了一个降序的序列
        while(hh <= tt && a[q[tt]] <= a[i]) tt --; 
        q[ ++ tt] = i;
        if(i >= k - 1)printf("%d ", a[q[hh]]);
    }
    return 0;
}

标签:窗口,队列,++,tt,最小值,int,hh,模板,单调
From: https://blog.51cto.com/u_15736437/6274862

相关文章

  • c++ class类bfs模板题目
    题目网址:走迷宫-题目-Liuser'sOJ(cpolar.cn)原本代码(bfs广度优先搜索):#include<bits/stdc++.h>usingnamespacestd;constintN=50;intn,m;intsx,sy;chara[N][N];intb[N][N];boolvis[N][N];intdx[]={1,0,-1,0};intdy[]={0,-1,0,1};structnode{i......
  • 生产者消费者模型,队列
    主要用来解耦,适合高并发场景、爬虫栈先进后出FILO借助队列实现FIFO队列是安全的不用加锁q.get()阻塞等待或取数据,如果有数据直接获取,如果没有数据就阻塞等待q.put()阻塞或放数据,如果可以放数据继续放,不可以放阻塞等待(IO操作)q.get_nowait()不阻塞,如果有数据直接获......
  • 栈、数组、队列、串(408)
    栈、数组、队列、串栈定义:删除和输入都在同一端的线性表,后进先出顺序栈定义一个线性表,用栈顶指针来控制栈元素的进出。链式栈定义一个头结点,一直指向栈顶,插入新结点时,更新头结点。优点:不会溢出,空间无限共享栈两个栈分别放在栈顶和栈底,存入的数据向中间靠齐。优点:节省存储......
  • 「模板」最长不下降子序列 LIS
    最长不下降子序列LIS在一个数字序列中,找到一个最长的子序列(可以不连续),使得这个子序列是不下降(非递减)的。例如,现有序列A={1,2,3,-1,-2,7,9}(下标从1开始),它的最长不下降子序列是{1,2,3,7,9},长度为5。另外,还有一些子序列是不下降子序列,比如{1,2,3},{-2,7,9}等,但都不是最长的......
  • 模板
    #include<iostream>using namespace std;template <class T,int n>class mysequence {T memblock[N];public:void setmember(int x,T value){memblock[x]=value; }T getmember(int x){return memblock[x];}}; int main(){mysequence<int......
  • 使用Pandoc构建Acm模板
    使用Pandoc构建Acm模板下周日打完河南ICPC省赛就要退役了,以后一场比赛前想要整理一下板子,想要一个拥有目录,页眉。页脚的Acm模板,这样就可以在比赛的时候快速翻阅,而且要更加好看但是存在的问题是:很多构建Acm模板的时候会使用Latex进行构建,但是我使用了很多,要么是些许麻烦,也许是我......
  • 标准模板11
    #include<iostream>#include<numeric>#include<functional>#include<vector>usingnamespacestd;intmain(){ intiarray[]={1,2,3,4,5}; vector<int>ivector(iarray,iarray+sizeof(iarray)/sizeof(int)); cout<<accumulate(ivector.beg......
  • 标准模板10
    #include<functional>#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;usingnamespaceplaceholders;intmain(){ intintArr[]={30,90,10,40,70,50,20,80}; constintN=sizeof(intArr)/sizeof(int); vector<int>......
  • 引用在模板推导中的基础逻辑
    reference引用是C++相对于C语言指针引入的一个新语法,可以以简单变量来使用指针。这种语法在使用的时候还是比较方便的,但是也在模板类型推导的过程中也带来了一些需要额外关注的细节。例子下面的例子中,rt是一个引用类型,问题是在模板参数函数Harry的定义中,模板参数TSECER并没有包......
  • Radis--消息队列
    引用:消息队列_哔哩哔哩_bilibili 1.消息队列的概念: 2.消息队列的工作机制: 注:Broker也可主动推送给consumer.3.Redis--MesssageQueue4.Redis--Pub/Sub5.Redis--Stream......