import java.util.*;

public class Test01 {
    public static void main(String[] args) {
        int[] num = new int[]{2,3,4,2,6,2,5,1};
        int size = 3;
        List<Integer> list = maxInWindows(num,size);
        System.out.println(list);

    }
    public static ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        if (size < 1 || size > num.length){
            return res;
        }
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < num.length; i++) {
            // i 其实就是窗口的右边界
            //队列添加元素，添加之前先将队列中小于自己的元素剔除
            //保证队列的左节点总是窗口中的最大值，保证队列是从左到右是单调递减的
            while (!deque.isEmpty() && num[deque.getLast()] < num[i]){
                deque.pollLast();
            }
            //注意添加的是元素下标
            deque.addLast(i);

            //队列中只能存窗口里的元素，当窗口划走后，需要将元素剔除
            while (!deque.isEmpty() && deque.getFirst() <= i - size){
                deque.pollFirst();
            }

            //将窗口中的最大值保存，i为窗口的右边界
            if (i >= size - 1){
                res.add(num[deque.getFirst()]);
            }
        }
        return res;
    }
}