$$\color{Red}{滑动窗口}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

思考

下面C++代码有按步的详细注释。此题最关键的是，我们为了既维护固定区间，又维护最值，只能妥协队列维护原数组下标，这样才既可以通过把下标值传入数组得到值的大小，又时刻可以通过i指针减去队列头部的值获取当前窗口大小

java容器

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main {
    static int N = (int) 1e6 + 10;
    static int n, k;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[] a = new int[N];
//    static int[] q = new int[N];
    static LinkedList<Integer> q = new LinkedList<Integer>();

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        k = Integer.parseInt(s1[1]);
        String[] s2 = br.readLine().split(" ");
        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(s2[i]);
        for (int i = 0; i < n; i++) {
            if (q.size() > 0 && i - k + 1 > q.peek()) q.pop();
            while (q.size() > 0 && a[i] <= a[q.getLast()]) q.remove(q.size() - 1);
            q.add(i);
            if (i >= k - 1) System.out.print(a[q.peek()] + " ");
        }
        q.clear();
        System.out.println();
        for (int i = 0; i < n; i++) {
            if(q.size() > 0 && i - k + 1 > q.peek()) q.pop();
            while (q.size() > 0 && a[i] >= a[q.getLast()]) q.remove(q.size() - 1);
            q.add(i);
            if (i >= k - 1) System.out.print(a[q.peek()] + " ");
        }
    }
}

java

import java.util.Scanner;
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;

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

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

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

python3

N = int(1e6 + 10)
# q存放的是array数组元素的下标
q = [0] * N
hh, tt = 0, -1
n, k = map(int, input().split())
array = [int(k) for k in input().split()]
#最小值
for i in range(len(array)):
    if tt >= hh and i - q[hh] + 1 > k:
        hh += 1
    while array[i] <= array[q[tt]] and tt >= hh:
        tt -= 1
    tt += 1
    q[tt] = i
    if i >= k - 1:
        print(array[q[hh]], end=' ')
print()
#最大值
hh, tt = 0, -1 #别忘了初始化队列指针
for i in range(len(array)):
    if tt >= hh and i - q[hh] + 1 > k:
        hh += 1
    while array[i] >= array[q[tt]] and tt >= hh:
        tt -= 1
    tt += 1
    q[tt] = i
    if i >= k - 1:
        print(array[q[hh]], end=' ')

C++

 #include <iostream>
using namespace std;

const int N = 1e6 + 10;
int a[N], q[N]; //q[]存放a[]中元素的下标

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i=0; i<n; i++)  scanf("%d", &a[i]);
    //队列头hh,队列尾tt
    int hh = 0, tt = -1;
    for(int i=0; i<n; i++)
    {
    /*  1.if语句
        维护固定长度的窗口,该判断，在窗口未满前不会被调用*/

        if(hh <= tt && i - q[hh] + 1 > k) hh++;
    /*    
        2.while循环-维持单调队列
          维护单调递增的队列元素，当要加入的元素比队列尾元素小，队列尾
          元素永远无法成为输出值，因此将它消除，进而使队列内部永远保持
          单调递增的 值们 它们所在下标的元素集合 （而且通过前面的判断
          该队列元素在输出前被限制在窗口大小内*/

        while(hh <= tt && a[q[tt]] >= a[i]) tt--;
    /*    
        3.队尾赋值
          此时队列元素大于等于1，且必定小于等于3，分类讨论：
          ①若不足三个: 插入到队尾，i++后，由于if语句的作用，可能元素不足
          窗口大小，但是窗口肯定还是要右移，因为我们窗口存放的，是可以
          成为答案的数据，并不是满三即输出，而是每次移动输出一次
          ②若超过三个：对我们输出无影响，只是i++ 进入下次循环后，会根据
          if语句的hh++ 将窗口范围缩小到3个内*/

        q[++tt] = i;

    //  4.队头按序输出，当且仅当i大于等于k-1，也就是满足已经扫描够3个元素

        if(i >= k-1)    printf("%d ", a[q[hh]]);

    }
    puts("");
    //最大值同理，只是维持单调递减序列
    hh = 0, tt = -1;
    for(int i=0; i<n; i++)
    {
    /*  1.if语句
        维护固定长度的窗口,该判断，在窗口未满前不会被调用*/

        if(hh <= tt && i - q[hh] + 1 > k) hh++;
    /*    
          2.while循环-维持单调队列
          维护单调递减的队列元素，当要加入的元素比队列尾元素大，队列尾
          元素永远无法成为输出值，因此将它消除，进而使队列内部永远保持
          单调递减的 值们 它们所在下标的元素集合 （而且通过前面的判断
          该队列元素在输出前被限制在窗口大小内*/

        while(hh <= tt && a[q[tt]] <= a[i]) tt--;
    /*    
        3.队尾赋值
          此时队列元素大于等于1，且必定小于等于3，分类讨论：
          ①若不足三个: 插入到队尾，i++后，由于if语句的作用，可能元素不足
          窗口大小，但是窗口肯定还是要右移，因为我们窗口存放的，是可以
          成为答案的数据，并不是满三即输出，而是每次移动输出一次
          ②若超过三个：对我们输出无影响，只是i++ 进入下次循环后，会根据
          if语句的hh++ 将窗口范围缩小到3个内*/

        q[++tt] = i;

    //  4.队头按序输出，当且仅当i大于等于k-1，也就是满足已经扫描够3个元素
        if(i >= k-1)    printf("%d ", a[q[hh]]);
    }

    puts("");

    return 0;
}