import java.util.Deque;
import java.util.LinkedList;
//自定義數(shù)組
class MyQueue {
    Deque<Integer> deque = new LinkedList<>();
    //彈出元素時，比較當(dāng)前要彈出的數(shù)值是否等于隊列出口的數(shù)值，如果相等則彈出
    //同時判斷隊列當(dāng)前是否為空
    void poll(int val) {
        if (!deque.isEmpty() && val == deque.peek()) {
            deque.poll();
        }
    }
    //添加元素時，如果要添加的元素大于入口處的元素，就將入口元素彈出
    //保證隊列元素單調(diào)遞減
    //比如此時隊列元素3,1，2將要入隊，比1大，所以1彈出，此時隊列：3,2
    void add(int val) {
        while (!deque.isEmpty() && val > deque.getLast()) {
            deque.removeLast();
        }
        deque.add(val);
    }
    //隊列隊頂元素始終為最大值
    int peek() {
        return deque.peek();
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 1) {
            return nums;
        }
        int len = nums.length - k + 1;
        //存放結(jié)果元素的數(shù)組
        int[] res = new int[len];
        int num = 0;
        //自定義隊列
        MyQueue myQueue = new MyQueue();
        //先將前k的元素放入隊列
        for (int i = 0; i < k; i++) {
            myQueue.add(nums[i]);
        }
        res[num++] = myQueue.peek();
        for (int i = k; i < nums.length; i++) {
            //滑動窗口移除最前面的元素，移除是判斷該元素是否放入隊列
            myQueue.poll(nums[i - k]);
            //滑動窗口加入最后面的元素
            myQueue.add(nums[i]);
            //記錄對應(yīng)的最大值
            res[num++] = myQueue.peek();
        }
        return res;
    }
}