【董晓算法】用存入下标的方法来巧解单调队列

本文主要是介绍【董晓算法】用存入下标的方法来巧解单调队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 前言：

本系列是看的B站董晓老师所讲的知识点做的笔记

董晓算法的个人空间-董晓算法个人主页-哔哩哔哩视频 (bilibili.com)

C单调队列

P1886 滑动窗口 /【模板】单调队列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

k为窗口的大小

维护最小值就是维护窗口内的升序子序列

维护最大值就是维护窗口内的降序子序列

思想:

q[]数组中存放的是元素的下标，队尾出队（判断大小）进队（存入下标），对头出队（判断距离）

 // 维护窗口最小值int h=1, t=0;                       //头尾指针初值for(int i=1; i<=n; i++){while(h<=t && a[q[t]]>=a[i]) t--; //队尾出队(队列不空且新元素更优)q[++t]=i;                         //队尾入队(存储下标 方便判断队头出队)if(q[h]<i-k+1) h++;               //队头出队(队头元素滑出窗口)if(i>=k) printf("%d ", a[q[h]]);  //输出最值}

这篇关于【董晓算法】用存入下标的方法来巧解单调队列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---