class Solution {

    public int[] maxInWindows(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return nums;
        }

        int[] res = new int[nums.length - k + 1];
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        int index = 0;
        for (int i = 0; i < nums.length; i++) {

            if (!queue.isEmpty() && i - queue.getFirst() >= k) {
                queue.pollFirst();
            }
            while (!queue.isEmpty() && nums[queue.getLast()] < nums[i]) {
                queue.pollLast();
            }
            queue.addLast(i);
            if (i >= k - 1) {
                res[index++] = nums[queue.getFirst()];
            }
        }
        return res;
    }
}