如果您已经有思路了，或者是N刷了，可以先自己写一遍。

题目分析

题目：给定一个数组和一个滑动窗口的大小，请找出所有滑动窗口里数值的最大值。例如，如果输入数组 [2, 3, 4, 2, 6, 2, 5, 1] 及滑动窗口的大小 3，那么一共存在 6 个滑动窗口，它们的最大值分别为 [4, 4, 6, 6, 6, 5]。

解题思路

要解决这个问题，我们可以使用双端队列（Deque）来维护当前窗口中最大值的索引。具体步骤如下：

使用双端队列存储当前窗口中可能成为最大值的元素的索引。
遍历数组，更新双端队列：
- 移除队列中不在当前窗口范围内的元素。
- 移除队列中小于当前元素的所有元素，因为这些元素不可能成为最大值。
将当前元素的索引加入到队列中。
当遍历的元素数目大于等于窗口大小时，将队列中的第一个元素（即当前窗口中的最大值）加入到结果列表中。

Java解法

下面是使用Java语言的解法：

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

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

        int n = nums.length;
        // 结果数组，用于存储每个窗口的最大值。
        int[] result = new int[n - k + 1];
        // 使用双端队列来存储窗口内的元素索引
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            // 移除队列中不在当前窗口范围内的索引
            if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }

            // 移除所有小于当前元素的队列中的元素
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            // 将当前元素的索引加入到队列中
            deque.offerLast(i);

            // 当遍历的元素数目大于等于窗口大小时，记录结果
            if (i >= k - 1) {
                // 将队列中的第一个元素（最大值）加入到结果数组中
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2, 3, 4, 2, 6, 2, 5, 1};
        int k = 3;
        int[] result = solution.maxSlidingWindow(nums, k);

        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

时间复杂度

这个方法的时间复杂度是 O(n)，因为每个元素最多只会被插入和删除队列一次。

空间复杂度

空间复杂度是 O(k)，因为双端队列中最多只会存储 k 个元素的索引。

References

239. 滑动窗口最大值 ↩︎

趣味算法题

双端队列：滑动窗口最大值