• 『单调队列』单调队列板子


    单调队列学习前提需知

    单调队列一般用于一类优化中,比如dp优化,或者二分的一系列题中,单调队列相比于同类型的单调栈而言,适用范围更广,考的范围也更广。单调队列是在一个长度为(n)的数列中,找到连续(m)个数,很快的求出其最大最小值

    算法内容

    竞赛需要用到胡点

    1、单调队列一般用于优化或者二分答案的判定中

    2、单调队列适用范围很广,建议集中练习

    单调队列求区间最大最小值略讲

    单调队列类似于一个双端队列的结构,其满足队列的从尾进从头出,也满足双端队列的从头出可以,从尾出也可以的形式,令进入的数有两个值,第一个值是进入的数本身有值,第二个值是进入的数有一个时间表示多久进入的,那么一定会满足的是,当当前数的价值大于(小于)队列中的从队尾开始的数时,那么就可以直接将队尾的数踢出,直到队列为空或者队列中有数大于(小于)当前的数为止,或者在队列的队首的时间已经在考虑区域外了了,那么我们就将队首弹出。通过这个思路,代码似乎就出来了

    比如我们求区间最小值,那么我们可以得到以下代码

    int front = 1, back = 0;
    	for (int i = 1; i <= n; i++) { 
    		if(q[front].idx + m < i) front++; //判断队首是否越界
    		while(front <= back && q[back].x >= arr[i]) back--; //查看进入的数是否小于队尾的数
    		back++; q[back].idx = i - 1, q[back].x = arr[i];
    		if(i >= m) printf("%d ", q[front].x);
    	} puts("");
    

    这就是我们的单调队列的整个代码了,以下代码参考滑动窗口

    //#define fre yes
    
    #include <cstdio>
    
    int n, m;
    
    const int N = 1000005;
    struct Node {
    	int idx, x;
    } q[N];
    int arr[N];
    
    int main() {
    	scanf("%d %d", &n, &m);
    	for (int i = 1; i <= n; i++) {
    		scanf("%d", &arr[i]);
    	}
    	
    	int front = 1, back = 0;
    	for (int i = 1; i <= n; i++) {
    		if(q[front].idx + m < i) front++;
    		while(front <= back && q[back].x >= arr[i]) back--;
    		back++; q[back].idx = i - 1, q[back].x = arr[i];
    		if(i >= m) printf("%d ", q[front].x);
    	} puts("");
    	
    	front = 1, back = 0;
    	for (int i = 1; i <= n; i++) {
    		if(q[front].idx + m < i) front++;
    		while(front <= back && q[back].x <= arr[i]) back--;
    		back++; q[back].idx = i - 1, q[back].x = arr[i];
    		if(i >= m) printf("%d ", q[front].x);
    	} return 0;
    }
    
  • 相关阅读:
    MySQL启动和关闭命令总结
    MySQL数据库5.6版本首次安装Root密码问题
    tomcat 9性能调优注意事项
    扫除减脂之路上的几个小障碍
    MySQL常见面试题
    关于邮箱发送邮件二之附件及图片
    关于邮箱发送邮件
    关于算法
    python中常见的数据类型
    C++实现复数类的输入输出流以及+-*/的重载
  • 原文地址:https://www.cnblogs.com/Nicoppa/p/11545302.html
一二三 - 开发者的网上家园