本文共 909 字，大约阅读时间需要 3 分钟。

单调队列

解决该类问题的重点维护一个队列，从队首到队尾是递减的，队首是最大的。队尾是最小的。

队尾接受值，队首排出值。

Java实现用双端队列，前面接收值，后面排出来值。

这类题目往往是跟滑动窗口一起出现的，在滑动窗口K的范围内查找最大最小值。

2.洛谷P1714切蛋糕

今天是小Z的生日，同学们为他带来了一块蛋糕。这块蛋糕是一个长方体，被用不同色彩分成了N个相同的小块，每小块都有对应的幸运值。

小Z作为寿星，自然希望吃到的第一块蛋糕的幸运值总和最大，但小Z最多又只能吃M小块(M≤N)的蛋糕。

吃东西自然就不想思考了，于是小Z把这个任务扔给了学OI的你，请你帮他从这N小块中找出连续的k块蛋糕(k≤M)，使得其上的幸运值最大。

输入格式

输入文件cake.in的第一行是两个整数N,M。分别代表共有N小块蛋糕，小Z最多只能吃M小块。

第二行用空格隔开的N个整数，第i个整数Pi代表第i小块蛋糕的幸运值。

输出格式

输出文件cake.out只有一行，一个整数，为小Z能够得到的最大幸运值。

输入输出样例

输入 #1复制

5 21 2 3 4 5

输出 #1复制

9

输入 #2复制

6 31 -2 3 -4 5 -6

输出 #2复制

5

维护一个最小的值；在单调队列中，队首最小，队首到队尾单调递增

import java.util.*; class Main{
       // 主函数public static void main(String[] args){
       Scanner sc = new Scanner(System.in);    int n = sc.nextInt();    int m = sc.nextInt();    int[] pre = new int[n];    // 前缀数组    for(int i=0;i
   
     queue = new LinkedList<>();    int res = Integer.MIN_VALUE;    // 滑动窗口 里面维护的一个最小的 即队首到队尾是递增的 队首是最小的    for(int i=0;i
   

转载地址：https://codingchaozhang.blog.csdn.net/article/details/115801654 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！