原始题目：剑指 Offer 59 - I. 滑动窗口的最大值 (opens new window)

解题思路：

滑动窗口在从左到右滑动的过程中，类似于一个大小为 $k$ 的队列在做出队和入队操作，将窗口的第一个元素出队，窗口的下一个元素入队。

因此问题可以转化为求一个队列里的最大值，最好拿到这个最大值的时间复杂度是 $O(1)$ 的。

本题可以用一个双端单调队列 $Deque$ 来维护滑动窗口的最大值。每次滑动窗口时，需要把窗口的第一个元素 $a$ 去掉，然后将窗口的下一个元素 $b$ 划入窗口中。

• 每次窗口划入下一个元素 $b$ 时，需要判断 $Deque$ 中的队尾元素是否小于 $b$，将小于 $b$ 的元素全部去掉，然后把 $b$ 插到队尾。
• 每次窗口去掉第一个元素 $a$ 时，需要判断 $a$ 是否等于 $Deque$ 的队头元素。如果是的话，要把 $Deque$ 的队头元素去掉。

这样维护之后， $Deque$ 将是一个非严格递减的队列，队头元素永远是当前窗口内的最大值。

代码：

public int[] maxSlidingWindow(int[] nums, int k) {
    if(nums == null || nums.length == 0 || k <= 0) {
        return new int[0];
    }
    int[] ans = new int[nums.length - k + 1];
    // 专门存放 [s, e] 区间内元素的最大值
    // deque 维护一个递减的队列
    Deque<Integer> deque = new LinkedList<>();
    int s = 0, e = 0;
    // 初始窗口
    while (e < k) {
        while (!deque.isEmpty() && deque.peekLast() < nums[e]) {
            deque.pollLast();
        }
        deque.offerLast(nums[e]);
        e++;
    }
    ans[0] = deque.peekFirst();
    int i = 1;
    while (e < nums.length) {
        // 滑动窗口的下一个元素入队
        while (!deque.isEmpty() && deque.peekLast() < nums[e]) {
            deque.pollLast();
        }
        deque.offerLast(nums[e]);
        // 滑动窗口的第一个元素出队
        if (!deque.isEmpty() && deque.peekFirst().equals(nums[s])) {
            deque.pollFirst();
        }
        ans[i++] = deque.peekFirst();
        s++;
        e++;
    }
    return ans;
}

复杂度分析：

• 时间复杂度$O(N)$：$N$ 为 $nums$ 数组的元素个数。每个元素最多需要入队和出队一次，因此单调队列的 $Deque$ 占用 $O(2N)$ 。
• 空间复杂度O(k)：辅助双端队列最多存放 $k$ 个元素，即窗口大小。