【Leetcode单调队列】- 洛谷P1714切蛋糕_切蛋糕差值最小leetcode

单调队列

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

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

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 2
1 2 3 4 5
1
2

输出 #1复制

9
1

输入 #2复制

6 3
1 -2 3 -4 5 -6
1
2

输出 #2复制

5
1

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

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<n;i++){
        pre[i] = sc.nextInt();
        if(i!=0) {
            pre[i] = pre[i] + pre[i-1];
        }
    }
    
    // 双端单调队列维护下标值
    Deque<Integer> queue = new LinkedList<>();
    int res = Integer.MIN_VALUE;
    // 滑动窗口 里面维护的一个最小的 即队首到队尾是递增的 队首是最小的
    for(int i=0;i<n;i++){
        while(!queue.isEmpty()&&pre[i]<pre[queue.getLast()]){
            // 队尾排出来
            queue.pollLast();
        }
        // 入队列
        queue.offerLast(i);
        // 控制最大值在滑窗范围内不在就排出来
        while(queue.peekFirst()+m<=i){
            queue.pollFirst();
        }
        
        // 不需要非得滑窗内记录值
        res = Math.max(res,pre[i]-pre[queue.peekFirst()]);
    }
    	// 输出结果
    	System.out.println(res);

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42