1.思路

这是一道经典题目，求滑动窗口的最大值和最小值。

我们先暴力方法找一下规律。我们可以直接遍历滑动窗口，找到最大值。在我们手动模拟遍历的时候可以发现，如果两个数都在滑动窗口内，并且右边的数比左边的数大，那么左边的数永远不可能是滑动窗口中最大值，因为右边的数比左边的数在滑动窗口的时间比左边的长。根据这个规律，我们可以用到队列来解决这个问题（这里我们是用数组模拟的队列）

以最小值为例，我们我们开始把原始数组存入队列中。如果队列为空就直接存入队列。如果队列不为空，但是要加入的元素比队首元素小那么就要移除队首元素，因为此时到以后，队头元素都不可能是最小值。注意：每一次要加入元素之前还要先判断队列中的元素是否已经滑出了滑动窗口，因为每一个元素最多在滑动窗口内存在k个时间。最大值就只要改一下符号就行，其余代码都一样。

2.代码模板

import java.io.*;
import java.util.*;
public class Main {
    static final int N = 1000010;
    static int[] queue = new int[N];    //模拟队列
    static int[] a = new int[N];    //原始数组
    static int hh = 0, tt = -1;     //队头和队尾
    static BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws Exception {
        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]); 
        int k = Integer.parseInt(str[1]); 
        str = br.readLine().split(" ");
        for(int i = 0; i < n; i++)
            a[i] = Integer.parseInt(str[i]);
        for(int i = 0; i < n; i++){
            if(hh <= tt && i - k + 1 > queue[hh])   //滑出了滑动窗口
                hh++;
            while(hh <= tt && a[queue[tt]] > a[i])  //如果要加入的元素小于队头，就把队头移除，因为此时到以后，队头元素都不可能是最小值
                tt--;
            queue[++tt] = i;    //把当前值加入队列（这里是添加的下标）
            if(i + 1 >= k)  //因为一刚开始滑动窗口还没到k，所以如果滑动窗口到k之后就开始输出
                bw.write(a[queue[hh]] + " ");
        }
        bw.write("\n");
        hh = 0;
        tt = -1;  
        for(int i = 0; i < n; i++){
            if(hh <= tt && i - k + 1 > queue[hh])
                hh++;
            //把`>`改成`<`就是找最大值，其余的代码都一样
            while(hh <= tt && a[queue[tt]] < a[i])
                tt--;
            queue[++tt] = i;
            if(i + 1 >= k)
                bw.write(a[queue[hh]] + " ");
        }   
        bw.write("\n");
        bw.flush();
        br.close();
        bw.close();
    }
}

3.复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)