一. AcWing154_滑动窗口

二. 理论

三. 代码

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e6+10;
namespace Question
{
    int n, k;
    int a[N];
}
using namespace Question;

namespace Queue
{
    int q[N], hh, tt=-1;//队列中存的是元素下标, 方便判断窗口大小
    
    void init()
    {
        hh=0, tt=-1;
    }
}
using namespace Queue;

signed main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
        scanf("%d", &a[i]);
    
    init();
    for(int i=0;i<n;i++)
    {
        while(hh<=tt&&q[hh]<i-k+1) hh++;//当队头不在窗口内
        while(hh<=tt&&a[q[tt]]>=a[i]) tt--;//当队尾元素的值比当前元素大时, 
        //永远不可能是答案, 弹出
        
        q[++tt]=i;//一定要先加入, 因为当前值可能是答案
        if(i-k+1>=0) printf("%d ", a[q[hh]]);//判断窗口大小是否为k, 不足k不输出
    }
    
    puts("");
    init();
    for(int i=0;i<n;i++)
    {
        while(hh<=tt&&q[hh]<i-k+1) hh++;//同上
        while(hh<=tt&&a[q[tt]]<=a[i]) tt--;//同上, 反过来
        
        q[++tt]=i;
        if(i-k+1>=0) printf("%d ", a[q[hh]]);
    }
}

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

class Window
{
    int hh, tt;
    int[] q = new int[Main.N];//队列存储的是下标，方便计算队列元素数量

    void init()
    {
        hh = 0;
        tt = -1;
    }
}

public class Main
{
    static final int N = (int) 1e6 + 10;
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static String[] it;

    static int n, k;
    static int[] a = new int[N];

    public static void main(String[] args) throws IOException
    {
        it = br.readLine().split(" ");
        n = Integer.parseInt(it[0]);
        k = Integer.parseInt(it[1]);
        it = br.readLine().split(" ");
        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(it[i]);
        Window w = new Window();
        w.init();

        for (int i = 0; i < n; ++i)
        {
            while (w.hh <= w.tt && w.q[w.hh] < i - k + 1) ++w.hh;//当前队头不在窗口内
            while (w.hh <= w.tt && a[w.q[w.tt]] >= a[i]) --w.tt;//当前队尾元素比当前元素大时
            //队尾元素永远不可能是最小值答案，弹出

            w.q[++w.tt] = i;//先加入, 有可能是答案, 索引
            if (i - k + 1 >= 0) bw.write(a[w.q[w.hh]] + " ");//窗口内单调递增，且窗口大小为k
        }

        bw.newLine();
        w.init();
        for (int i = 0; i < n; ++i)
        {
            while (w.hh <= w.tt && w.q[w.hh] < i - k + 1) ++w.hh;//当前队头不在窗口内
            while (w.hh <= w.tt && a[w.q[w.tt]] <= a[i]) --w.tt;//当前队尾元素比当前元素小时
            //队尾元素永远不可能是最小值答案，弹出

            w.q[++w.tt] = i;//先加入有可能是答案
            if (i - k + 1 >= 0) bw.write(a[w.q[w.hh]] + " ");//窗口内单调递减，且窗口大小为k
        }
        bw.close();
    }
}