蓝桥杯---附近最小（典型的滑动窗口类型问题）

题目链接：附近最小

import java.util.ArrayDeque;
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
   static int n;
   static int[] a;
   static int k;

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        a=new int[n+1];
        for(int i=1;i<=n;i++){
            a[i]=scanner.nextInt();
        }
        k=scanner.nextInt();
        ArrayDeque<Integer> q=new ArrayDeque<>();//双向队列

        //维持队列的单调性，最小的在队头
        for(int i=1;i<=k+1;i++){
            while(!q.isEmpty()&&i<n&&a[i]<a[q.peekLast()]){
                q.removeLast();
            }
            q.addLast(i);
        }
        int[] mi=new int[n+1];//表示第i处的相应区间的最小值
        mi[1]=q.peekFirst();
        for(int i=2;i<=n;i++){
            //先看左边界有没有超出
            if(!q.isEmpty()&&q.peekFirst()<i-k&&i-k>0){
                q.removeFirst();
            }
            while(!q.isEmpty()&&i+k<=n&&a[i+k]<=a[q.peekLast()]){
                q.removeLast();
            }
            //这个地方出过错，着重标记
            //后面添加的元素都是i+k，而不是i
            if(i+k<=n){
                q.addLast(i+k);
            }
           mi[i]=q.peekFirst();
        }
        for(int i=1;i<=n;i++){
            System.out.print(a[mi[i]]+" " );
        }
    }
}