自己实现队列

滑动窗口问题（154题）是在窗口大小为m的范围内寻找最大值 i - q[hh] + 1 > m则弹出队头，i - q[hh] + 1为滑动窗口长度，m为题目的约束长度，q[hh]记录滑动窗口的左端点

本题求长度不超过m的最大子序和，以i为终点包括i往前最多选m个点的前缀和最大值，res = max(s[i] - s[(i-m+1) - 1])，q[hh]记录的(i-m+1) - 1为左端点的前一个点, 队头弹出条件为i - (q[hh] + 1) + 1 > m，化简得i - q[hh] > m

索引位置

给定左端点i和右端点j，长度为：len = i - j + 1

给定左端点i和长度len，右端为：j = i + len - 1

给定右端点j和长度len，左端为：i = j - len + 1

import java.util.*;
class Main{
    private static int inf = (int) 1e9;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] s = new int[n+1];
        for(int i = 1; i <= n; i++){
            s[i] = sc.nextInt();
            s[i] += s[i-1];
        }

        int[] q = new int[n+1];
        int hh = 0, tt = 0, res = -inf;
        for(int i = 1; i <= n; i++){
            if(hh <= tt && i - q[hh] > m) hh++;
            res = Math.max(res, s[i] - s[q[hh]]);
            while(hh <= tt && s[q[tt]] >= s[i]) tt--;
            q[++tt] = i;
        }
        System.out.println(res);
    }
}

使用Deque

注：队列中保存的是数组的下标用于判断滑动窗口的大小i - q.peek() > m 错误写法if(q.size() > m)

import java.util.*;
class Main{
    private static int inf = (int) 1e9;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] s = new int[n+1];
        for(int i = 1; i <= n; i++){
            s[i] = sc.nextInt();
            s[i] += s[i-1];
        }
        Deque<Integer> q = new LinkedList<>();
        q.add(0);
        int res = -inf;
        for(int i = 1; i <= n; i++){
            if(!q.isEmpty() && i - q.peek() > m) q.poll();
            res = Math.max(res, s[i] - s[q.peek()]);
            while(!q.isEmpty() && s[q.peekLast()] >= s[i]) q.pollLast();
            q.add(i);
        }
        System.out.println(res);
    }
}