11. 滑动窗口的最大值

给你一个整数数组nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。要求返回滑动窗口中的最大值 。

1. 解法 - 双端队列

public int[] maxSlidingWindow(int[] nums, int k) {

        // 检查输入的有效性
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }

        int resIndex = 0;

        // 结果数组
        int[] result = new int[nums.length - k + 1];

        // 双端队列，用于存储窗口内的元素索引
        LinkedList<Integer> deque = new LinkedList<>();

        // 遍历数组
        for(int i = 0; i < nums.length; i++) {

            // 滑动窗口的范围是从 i - k + 1 到 i (包括两端)
            // 移除超出窗口范围的索引
            while(!deque.isEmpty() && deque.peekFirst() < i - k + 1 ) {
                deque.pollFirst();
            }

            // 删除所有比新入队列小的元素
            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.pollLast();
            }

            // 将当前的索引添加到队列的尾部
            deque.offerLast(i);

            // 当窗口的大小为k时记录最大值
            if (i >= k - 1) {
                result[resIndex++] = nums[deque.peekFirst()];
            }

        }

        return result;
    }