/**
1. 滑动窗口最大值 -> 动态区间最大值 -> 单调队列
2. 维护一个单调递减的队列, 那么队头就是当前区间最大值
    2.1 滑出的数等于队头时弹出队头
    2.2 压入x时存在小于x的数全部c从尾部弹出, 因为如果比新加入的还小,那它肯定不是结果
*/

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> queue  = new LinkedList<>();
        List<Integer> result = new ArrayList<>();
        for (int i = 0 ; i < k; i++){
            while (!queue.isEmpty() && queue.peekLast() < nums[i]) queue.pollLast();
            queue.offerLast(nums[i]);
        }
        result.add(queue.peekFirst());
        for (int i = 1, j = k, n = nums.length; i < n && j < n; i++, j ++){
            if (!queue.isEmpty() && nums[i-1] == queue.peekFirst()) queue.pollFirst();
            while (!queue.isEmpty() && queue.peekLast() < nums[j]) queue.pollLast();
            queue.offerLast(nums[j]);
            result.add(queue.peekFirst());
        }
        int[] max = new int[result.size()];
        for (int i = 0; i < result.size(); i++) max[i] = result.get(i);
        return max;
    }
}