剑指 Offer 59 - I. 滑动窗口的最大值

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例 1：

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释:

滑动窗口的位置最大值

[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7

提示：

你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

题解一单调队列

要求滑动窗口内的最大值，首先想到的是双向队列，一边推窗一边保持最大元素在队首。由于要确保窗口长度，队列中存的是下标。

public int[] maxSlidingWindow(int[] nums, int k) {
    int[] res = new int[nums.length - k + 1];
    Deque<Integer> deque = new ArrayDeque<>();
    for (int i = 0; i < nums.length; ++i) {
        if (!deque.isEmpty() && deque.peekFirst() == i - k) {
            deque.removeFirst();
        }
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.removeLast();
        }
        deque.addLast(i);
        if (i >= k - 1) {
            res[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return res;
}

题解二双向遍历

如果通过固定队列长度可以来限制搜索范围，通过双向遍历也可以。不依靠队列的话有个问题，最大值会不断传播，如果 [0] 处是数组最大值，这一最大值可以一直传播到队尾。那我们必须进行适当的划分，让最大值最远传播 k 个数字（包含自己）。

我们直接将队列分成一段段长为 k 的区间，每一段区间中，第一次遍历取得前半段（[0.. i % k]）上的最大值。

for (int i = 0; i < n; ++i) {
    if (i % k == 0) {
        prefixMax[i] = nums[i];
    }
    else {
        prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);
    }
}

然后从后向前进行一次遍历，取得后半段（[i % k .. k - 1]）上的最大值。

for (int i = n - 1; i >= 0; --i) {
    if (i == n - 1 || (i + 1) % k == 0) {
        suffixMax[i] = nums[i];
    } else {
        suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);
    }
}

然后，我们要取以 i 为起点长度为 k 的窗口的最大值，实际要取的就是当前区间上 [i % k .. k - 1] 上的最大值，和下一区间 [0 .. (i - 1 + k) % k] 上的最大值。

完整答案

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    if (n == 0) {
        return new int[0];
    }
    int[] prefixMax = new int[n];
    int[] suffixMax = new int[n];
    for (int i = 0; i < n; ++i) {
        if (i % k == 0) {
            prefixMax[i] = nums[i];
        }
        else {
            prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);
        }
    }
    for (int i = n - 1; i >= 0; --i) {
        if (i == n - 1 || (i + 1) % k == 0) {
            suffixMax[i] = nums[i];
        } else {
            suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);
        }
    }
    int[] ans = new int[n - k + 1];
    for (int i = 0; i <= n - k; ++i) {
        ans[i] = Math.max(suffixMax[i], prefixMax[i + k - 1]);
    }
    return ans;
}

剑指 Offer 59 - I. 滑动窗口的最大值

题解一 单调队列

题解二 双向遍历

题解一单调队列

题解二双向遍历