二维单调队列(模板)

单调队列的实现(以最小值为例)

1维护单调性

队列中的元素保持单调递增(头到尾)对头最小

2窗口内元素的更新

队列中所存储的元素为候选值的下标

每次加入新的元素时，先维护队列的单调性

如果对尾的元素比新加入的元素大，说明该元素是不可能成为有新元素存在时窗口的最小值，可以移除

3移除过期元素

队头元素是最小的元素也是最先进入队列的元素，随着队列向右移动，需要检查对头是否还在窗口的内部，满足i - q[hh] >= k就可以移除

朴素代码实现

注意一下hh和tt的初始化即可

import java.io.*;

public class Main {
    static final int N = 1000010;
    static int[] a = new int[N], q = new int[N];
    static int n, k, hh, tt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        k = Integer.parseInt(str[1]);
        str = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) a[i] = Integer.parseInt(str[i - 1]);

        hh = 0; tt = -1;
        for (int i = 1; i <= n; i++) {
            if (hh <= tt && i - q[hh] >= k) hh++;
            while (hh <= tt && a[q[tt]] >= a[i]) tt--;
            q[++tt] = i;
            if (i >= k) out.print(a[q[hh]] + " ");
        }
        out.println();

        hh = 0; tt = -1; q[0] = 0;
        for (int i = 1; i <= n; i++) {
            if (hh <= tt && i - q[hh] >= k) hh++;
            while (hh <= tt && a[q[tt]] <= a[i]) tt--;
            q[++tt] = i;
            if (i >= k) out.print(a[q[hh]] + " ");
        }
        out.flush();
    }
}

可以写成一个方法进行传参数区分两个队列

java双端队列的实现(ArrayDeque或者LinkedList)(灵活性强, 会稍微慢点, 但不多)

import java.io.*;
import java.util.*;

public class Main {
    static final int N = 1000010;
    static int[] a = new int[N];
    static int n, k;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        k = Integer.parseInt(str[1]);
        str = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) a[i] = Integer.parseInt(str[i - 1]);

        LinkedList<Integer> q = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            if (!q.isEmpty() && i - q.getFirst() >= k) q.removeFirst();
            while (!q.isEmpty() && a[q.getLast()] >= a[i]) q.removeLast();
            q.addLast(i);
            if (i >= k) out.print(a[q.getFirst()] + " ");
        }
        out.println();
        q.clear();
        for (int i = 1; i <= n; i++) {
            if (!q.isEmpty() && i - q.getFirst() >= k) q.removeFirst();
            while (!q.isEmpty() && a[q.getLast()] <= a[i]) q.removeLast();
            q.addLast(i);
            if (i >= k) out.print(a[q.getFirst()] + " ");
        }
        out.flush();
    }
}