public int[] maxSlidingWindow(int[] nums, int k)
    {
        if (nums.length == 0) {
            return new int[0];
        }
        
        int resultSize = nums.length - k + 1;
        int[] result = new int[resultSize];

        int offset = k - 1;

        // Use a double ended queue which maintains ordering
        // The top of the queue is always the largest element in the queue
        Deque<Integer> windowDeque = new LinkedList<Integer>();

        for (int i = 0; i < nums.length; ++i) {

            if (!windowDeque.isEmpty() && windowDeque.peek() <= i - k) {
                windowDeque.poll();
            }

            int currentNum = nums[i];

            while (!windowDeque.isEmpty() && nums[windowDeque.peekLast()] < currentNum) {
                windowDeque.pollLast();
            }
            
            windowDeque.offer(i);
            int resultIndex = i - offset;
            if (resultIndex  >= 0) {
                result[resultIndex] = nums[windowDeque.peek()];
            }
        }
        return result;
    }