2、滑动窗口&单调队列

AcWing 154. 滑动窗口

直接使用Deque作为双端队列

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

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.dandiaoduilie();
        out.flush();
    }

    //双端队列Deque
    //min应该递增||非减
    Deque<Integer> queue_min = new ArrayDeque<>();
    //max应该递减||非增
    Deque<Integer> queue_max = new ArrayDeque<>();
    static PrintWriter out = new PrintWriter(System.out);

    void dandiaoduilie() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();//数组的元素个数
        int k = scanner.nextInt();//滑动窗口的大小
        int nums[] = new int[n];
        for (int i = 0; i < n; i++) nums[i] = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            //滑动窗口不在区间内的时候
            if(!queue_min.isEmpty()&&queue_min.peekFirst()<=i-k) queue_min.removeFirst();
            //当尾队列的元素一直大于等于nums[i]的时候，尾出列
            while(!queue_min.isEmpty()&&nums[queue_min.peekLast()]>=nums[i]) queue_min.removeLast();
            queue_min.offerLast(i);
            if (i >= k - 1)
                out.print(nums[queue_min.peekFirst()] + " ");
        }
        out.println();
        for (int i = 0; i < n; i++) {
            //滑动窗口不在区间内的时候
            if(!queue_max.isEmpty()&&queue_max.peekFirst()<=i-k) queue_max.removeFirst();
            //当尾队列的元素一直小于等于nums[i]的时候，尾出列
            while(!queue_max.isEmpty()&&nums[queue_max.peekLast()]<=nums[i]) queue_max.removeLast();
            queue_max.offerLast(i);
            if (i >= k - 1)
                out.print(nums[queue_max.peekFirst()] + " ");
        }
    }
}

数组模拟双端队列

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

public class Main
{
    static final int N = (int)1e6 + 10;
    static int[] a = new int[N], q = new int[N];
    static int hh = 0, tt = -1;
    static Scanner in = new Scanner(System.in);
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args)
    {
        int n = in.nextInt(), m = in.nextInt();
        for (int i = 0; i < n; i++) a[i] = in.nextInt();
        for (int i = 0; i < n; i++)
        {
            if (hh <= tt && i - q[hh] + 1 > m) hh++;
            while (hh <= tt && a[q[tt]] >= a[i]) tt--;
            q[++tt] = i;
            if (i >= m - 1)
                out.print(a[q[hh]] + " ");
        }
        out.print("\n");

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

}