class Solution {
    public int[] maxInWindows(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            if (!deque.isEmpty() && i - deque.peekFirst() +1 > k) {
                deque.removeFirst();//最大值出队
            }

            while(!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.removeLast();
            }
            deque.addLast(i);
            if (i >= k -1) {
                res.add(nums[deque.peekFirst()]);
            }
        }

        return res.stream().mapToInt(value -> value).toArray();
    }
}