单调队列
P1886 滑动窗口 /【模板】单调队列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目大意:给出一个长度为 n
的数组,编程输出每 k
个连续的数中的最大值和最小值。 单调队列:队尾进队,队尾出队,对头出队(维护队列的单调性) 实现方法:数组加两个指针,或者 #inclued <deque>
性质:
- 队尾出队条件:队列不空且新元素更优(即更大或者更小,或其他判定条件),队中旧元素从队尾出队
- 左侧为对头,右侧为队尾,每个元素都必然从队尾进队一次
- 队头出队条件:对头元素划出了窗口,也就是该元素无用了
- 注意:队列中存储元素的下标,方便判断队头出队
- 队头即当前的最优值
代码:
[[背包#单调队列 优化|应用]]