滑动窗口问题

leetcode方法：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] q = new int[n];
        int hh = 0, tt = -1;
        int[] res = new int[nums.length - k + 1];
        if(n == 0) return new int[0];
        int idx = 0;
        for(int i = 0; i < n; i++){
            if(hh <= tt && q[hh] < i - k + 1) hh++;
            while(hh <= tt && nums[i] >= nums[q[tt]]) tt--;
            q[++tt] = i; //把当前元素的索引存入队列
            if(i >= k - 1) res[idx++] = nums[q[hh]];
        }
        return res;
    }
}

import java.util.*;

class Main{

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int N = 1000010;
        int[] a = new int[N];
        int[] q = new int[N]; //这个数组用来存放当前队列内各元素在a中的索引
        for(int i = 0; i < n; i++){
            a[i] = in.nextInt();
        }

        int hh = 0, tt = -1;
        for(int i = 0; i < n; i++){
            if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;  // 判断队头是否滑出窗口，如果出窗了，就需要把队头元素删掉
            while (hh <= tt && a[q[tt]] >= a[i]) tt -- ;  //如果当前元素小于等于队尾元素，则需要把队尾元素删掉
            q[++ tt] = i; //把当前元素的索引存入队列
            if (i >= k - 1) {
                System.out.print(a[q[hh]] + " ");//如果过了开始的那几个不全的数（窗口开始变得完整），就可以输出队列头部元素了。
            }
        }
        System.out.println("");
        hh = 0;
        tt = -1;
        for(int i = 0; i < n; i++){
            if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;
            while (hh <= tt && a[q[tt]] <= a[i]) tt -- ;
            q[++ tt] = i;
            if (i >= k - 1) {
                System.out.print(a[q[hh]] + " ");
            }
        }

    }


}