ac

有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置，求每一种窗口状态下的最大值。（如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值）

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception{
        String line;
        String[] strArr;
        line = reader.readLine();
        strArr = line.split(" ");
        int n = Integer.valueOf(strArr[0]);
        int w = Integer.valueOf(strArr[1]);

        line = reader.readLine();
        strArr = line.split(" ");

        int arrMaxVal = Integer.MIN_VALUE;
        int[] arr = new int[n];
        for(int i=0;i<n;i++) {
            int val = Integer.valueOf(strArr[i]);
            arr[i] = val;
            if(val > arrMaxVal){
                arrMaxVal = val;
            }
        }
        if(w <= 0 ){
            System.out.println(0);
            return;
        }
        if(w >= n){
            System.out.println(arrMaxVal);
            return;
        }
        int[] res = new int[n - w + 1];
        // 双端队列存放下标
        LinkedList<Integer> queue = new LinkedList();
        for(int i=0;i<n;i++){
            if(queue.isEmpty()){
                queue.addLast(i);
            }else {
                while (!queue.isEmpty()) {
                    int lastIndex = queue.peekLast();
                    if (arr[lastIndex] <= arr[i]) {
                        queue.pollLast();
                    }else {
                        break;
                    }
                }
                queue.offerLast(i);
                if (i - queue.getFirst() > (w - 1)) {
                    queue.pollFirst();
                }
            }
            if(i >= w-1) {
                res[i - (w-1)] = queue.getFirst();
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<res.length - 1;i++){
//            System.out.print(arr[res[i]] + " ");
            sb.append(arr[res[i]] + " ");
        }
//        System.out.println(arr[res[res.length-1]]);
        sb.append(arr[res[res.length-1]]);
        System.out.println(sb.toString());
    }

}
/*
8 3
4 3 5 4 3 3 6 7

5 5 5 4 6 7
*/

import java.util.*;


public class Main {

    public static Scanner sc = new Scanner(System.in);

    /*
8 3
4 3 5 4 3 3 6 7
     */
    public static void main(String[] args) {

        int n = sc.nextInt();
        int w = sc.nextInt();
        int[] arr = new int[n];
        int arrMaxVal = Integer.MIN_VALUE;
        for(int i=0;i<n;i++) {
            int val = sc.nextInt();
            arr[i] = val;
            if(val > arrMaxVal){
                arrMaxVal = val;
            }
        }
        if (n <= 0) {
            System.out.print("");
            return;
        }
        if(w >= n){
            System.out.println(arrMaxVal);
            return;
        }
        int[] res = new int[n - w + 1];
        // 双端队列存放下标
        LinkedList<Integer> queue = new LinkedList();
        for(int i=0;i<n;i++){
            if(queue.isEmpty()){
                queue.addLast(i);
            }else {
                int firstIndex = queue.getFirst();
                if(i - firstIndex > (w-1) ){
                    queue.pollFirst();
                }
                while(!queue.isEmpty()){
                    int lastIndex = queue.peekLast();
                    if(arr[lastIndex] <= arr[i]){
                        queue.pollLast();
                    }else {
                        break;
                    }
                }
                queue.offerLast(i);
            }
            if(i >= w-1) {
                res[i - (w-1)] = queue.getFirst();
            }
        }
        for(int i=0;i<res.length - 1;i++){
            System.out.print(arr[res[i]] + " ");
        }
        System.out.println(arr[res[res.length-1]]);
    }

}