单调队列
P1886 滑动窗口 /【模板】单调队列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目大意：给出一个长度为 n 的数组，编程输出每 k 个连续的数中的最大值和最小值。 单调队列：队尾进队，队尾出队，对头出队（维护队列的单调性） 实现方法：数组加两个指针，或者 #inclued <deque> 性质：
- 队尾出队条件：队列不空且新元素更优（即更大或者更小，或其他判定条件），队中旧元素从队尾出队
- 左侧为对头，右侧为队尾，每个元素都必然从队尾进队一次
- 队头出队条件：对头元素划出了窗口，也就是该元素无用了
- 注意：队列中存储元素的下标，方便判断队头出队
- 队头即当前的最优值
代码：
CPP
12345678910111213141516deque <int> dq;
int h=1,t=0;
for (int i=1;i<=n;i++){
while (!dq.empty()&&num[dq.back()]>=num[i]){
//队尾出队
dq.pop_back();
}
//新的优解入队
dq.push_back(i);
if (dq.front()<i-k+1){
//过期元素队头出队
dq.pop_front();
}
//以第i个数结尾的长度为k的数组的最小值
cout<<num[dq.front()]<<" ";
}
[[背包#单调队列 优化|应用]]