class Solution{
    public int[]  maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0)
            return new int[0];

        List<Integer> list = new ArrayList<>();
        Deque<Node> deque = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            int curr = nums[i];
            if (i >= k - 1) {
                int indexToRemove = i - (k - 1);
                addAndCompress(deque, Node.of(i, nums[i]));
                Node first = deque.getFirst();
                if (first.index == indexToRemove) deque.removeFirst();
                list.add(first.val);
            } else {
                addAndCompress(deque, Node.of(i, curr));
            }

        }


        return toArray(list);
    }

    private void addAndCompress(Deque<Node> deque, Node curr) {
        if (deque.isEmpty()) {
            deque.add(curr);
            return;
        }
        while (true) {
            if (deque.getLast().val <= curr.val) {
                deque.removeLast();

                if (deque.isEmpty()) {
                    deque.add(curr);
                    return;
                }
            }
            else {
                deque.addLast(curr);
                return;
            }
        }
    }

    static class Node {
        int index;
        int val;

        public Node(int index, int val) {
            this.index = index;
            this.val = val;
        }

        static Node of (int index, int val) {
            return new Node(index, val);
        }
    }

    private int[] toArray(List<Integer> list) {
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

}